[BOJ][C++] 백준 1789번: 수들의 합

문제

https://www.acmicpc.net/problem/1789

 

문제 이해

서로 다른 N개의 자연수의 합이 S이다. S가 주어질 때 N의 최댓값을 구한다.

 

문제 풀이

💡 아이디어

• N이 최대가 되려면, 자연수를 1부터 차례대로 더하는 방식을 생각할 수 있다.
• 1 + 2 + 3 + 4 + ... = S 이런식으로 더할 경우 N이 최대가 된다.
• 1 + 2+ 3 + ... + n = n * (n + 1) / 2 인 점을 이용해서 예시를 살펴볼 수 있다.
• 예: 200
  
  • 1 + 2 + 3 + ... + 18 + 19 = 190 에서 10을 더하면, 서로 다른 수라는 조건을 만족하지 못한다.
  • 1 + 2 + 3 + ... + 17 + 18 = 171 이므로, 29를 더하면 200이 된다.
  • N의 최댓값은 19이다.

 

🔨 구현

• 반복문을 이용하여 S에서 자연수 1부터 차례대로 뺀다.
• 종료 조건은 S가 0보다 작아지면 더이상 뺄 수 없음을 이용한다.

 

🚨 S의 크기

      S의 최대 크기는 4,294,967,295이므로 int 범위를 초과한다.

 

코드

#include<iostream>

using namespace std;

int main() {

    long long s;
    int n = 1;
    cin >> s;

    while (s >= n) {
        s -= n++;
    }

    cout << n - 1;

    return 0;
}