[1789] 수들의 합

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

1789번: 수들의 합

<문제>

최저의 경우는, 1 + 2 + 3 + ... + N-2 + N-1 + N 과 같은 경우일 것이므로

1부터 N까지의 누적합이 초과하기 '이전의' N을 초과하면 된다.

 

1부터 N까지의 누적합을 dp[n]에 넣는다면, 'dp[n] < S' 을 만족하는 최대의 n이 곧 최적해가 되겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int main(void) {
    long long n, i, sum = 0;
    cin >> n;
    for (i = 1;; i++) {
        sum += i;
        if (sum > n) break;
    }
    cout << i - 1;
    return 0;
}