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

[Silver V] 1789 : 수들의 합

문제 링크

분류

그리디 알고리즘, 수학

문제 설명

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

입력

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.

출력

첫째 줄에 자연수 N의 최댓값을 출력한다.

---

풀이

소스 코드

---

#include <iostream>
using namespace std;

int main() {
    long long s;
    long long sum = 0;
    int num = 1;

    cin >> s;

    while (true) {
        sum += num;
        if (sum > s) {
            num--;
            break;
        }
        num++;
    }

    cout << num << endl;
}

설명

---

서로 다른 자연수를 가장 많이 더해서 수를 만드는 방법은 간단합니다. 1부터 계속 더하면 됩니다.

문제는 어떻게 수 S를 만드는가입니다. 꽤 오래 고민했는데 생각보다 매우 쉬운 이야기였습니다.
1부터 n개의 자연수를 쭉 더하다가 S를 넘은 시점에, n-1개가 정답입니다.

• 예시로 자연수 S를 200으로 둡시다.
  1+2+3+4 + ... 의 식으로 더합니다. 1+2+3+4+ ... +20 = 210 입니다.

  200을 넘어섰으니 다시 20을 빼고 생각합니다.
  1+2+3+4+ ... +19 = 190 에서, 19를 29 으로 바꾸면 200이 됩니다.
  따라서 정답은 20 - 1 = 19 입니다.

• 또 다른 예시를 들어봅시다. 이번에는 S를 20으로 생각하겠습니다.
  1+2+3+4+5+6 = 21입니다. 20을 넘었으므로 6을 빼면 1+2+3+4+5 = 15입니다. 이제 5를 10으로 바꾸면 20이네요. 정답은 6 - 1, 5입니다.

다른 풀이

---

이분 탐색 (Binary Search)를 활용한 풀이도 참고해보시기 바랍니다.

// Authored by : tony9402
// Co-authored by : -
// Link : http://boj.kr/b757695822a7451ca902c666e024bb5f
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

ll S;
bool chk(ll n){ return n*(n+1)/2 > S; }

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> S;
    ll l = 1, r = 93000; // sqrt(4294967295 * 2)
    while(l <= r){
        ll mid = (l + r) / 2;
        if(chk(mid))r = mid - 1;
        else l = mid + 1;
    }
    cout << r;
}

소스 코드 출처 | Github baekjoon

(C++) 백준 1789번 - 수들의 합 (이진 탐색)