[BOJ/C++] 수들의 합(1789번)

1. 개요

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

1789번: 수들의 합

1-1. 설명

서로 다른 N개의 자연수 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 무엇인지 구하는 프로그램을 작성한다.

1-2. 제한 사항

 - 첫 줄에 자연수 S가 주어지며, S는 1 이상 4,294,967,295 이하

---

2. 구현

2-1. 풀이

최댓값을 구하기 위해 1부터 차례대로 더해보면 S와 같거나 클 때가 있다. 같으면 그 수를 그대로 반환하면 되지만, 클때는 1을 한번 빼주어 반환하면 된다. 최근에 더한 수로 인해 크게 변한다면 최근 수를 더하지 말고 그 전의 수를 조금 더 큰 수로 바꿔주면 되기 때문이다. 

2-2. 코드

#include <iostream>
using namespace std;


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    long long S, sum = 0, N = 0;
    cin >> S;

    for (int i = 1; i <= S + 1; i++) {
        if (sum == S) break;
        else if (sum < S) {
            sum += i;
            N += 1;
        }
        else if (sum > S) {
            N -= 1;
            break;
        }
    }
    cout << N << "\n";
    return 0;
}