[BAEKJOON] 1789 수들의 합 (C++)

[ 문제 ]

문제

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

입력

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

---

[ 조건 및 풀이 ]

이분탐색으로 간단하게 하는방법과, 처음수부터 더해가는 방법이있다.

(1) 이분탐색의 경우

Sigma N = N x (N+1) / 2 공식이 필요하다.

 

(2) 처음수부터 더해가는 경우

최대값이 나와야하므로 1부터 더해간다 했을때,

더해가는 값이 입력값보다 커지는경우 최대갯수라 할 수 있다.

더해가던값이 15인데 입력값이 17이라면,

1+2+3+4+5 -> 1+2+3+4+(5->7) 로 변하게되어 최대갯수라 판단할 수 있기 때문.

---

[ 핵심소스코드 / C++ ]

ll value = sqrt(input * 2);
ll result = value * (value + 1)/2;

[ 전체소스코드 / C++ ] 

// 이분탐색
#include <iostream>
#include <cmath>
#pragma warning(disable:4996)
using namespace std;

#define ll long long

void solve(ll input) {
    ll index = sqrt(input * 2);
    while (true) {
        ll result = index * (index + 1)/2;
        if (result > input) index--;
        else {
            cout << index;
            return;
        }
    }
}
int main() {
#ifdef _CONSOLE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ll res;
    cin >> res;
    solve(res);
}

// 수 더해가기
#include <iostream>
#include <cmath>
#pragma warning(disable:4996)
using namespace std;

#define ll long long

void solve(ll input) {
    ll idx = 0;
    ll result = 0;
    while(true) {
        result += ++idx;
        if (result >= input) {
            if (result > input)
                idx--;
            cout << idx;
            return;
        }
    }
}
int main() {
#ifdef _CONSOLE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ll res;
    cin >> res;
    solve(res);
}