[C++] 백준 온라인 저지 1789번 수들의 합 풀이

자연수 N개의 수들의 합 S를 만들 수 있는 수들 중 N의 최댓값을 구하는 문제 

 

---

문제의 조건

 

1. 수들의 합 S가 주어진다. 

 

2. 자연수 N의 최댓값을 출력한다. 

 

---

풀이 과정

 

첨 봤을 땐 뭐 이런 문제가 있나... 했는데

누적합계를 구하면서 나오는 최댓값을 구하면 되나 싶어서 누적합계를 구해 봤습니다. 

근데 애매하게 틀린 숫자가 나오고 문제 자체도 이해가 잘 안 가서 힌트를 찾아봤습니다. 

 

문제 이해 후 정리된 풀이

1. 누적합계를 구하는 방식으로 접근하는 것은 맞다. 

 

2. 하지만 모든 수가 연속된 숫자일 필요는 없다. 

S = 5 라면

[1,1,1,1,1] 로도 5를 만들 수 있다. 

이 경우엔 N개의 자연수 중 최댓값은 1이라고 할 수 있지만 유일하게 1만 있는 것이 아니다. 

5를 만들기 위해서 1을 다섯번 더할 수도 있지만

2+3 = 5 은 훨씬 적은 횟수의 계산을 하면서 N개의 자연수 중 유일한 최댓값 3도 구할 수 있다. 

 

3. 그래서 1부터 N까지의 누적합계를 구하는데 

누적합계가 S를 넘어간다면 마지막으로 더한 N을 빼고 그 N보다 작으면서 정확하게 S를 만들 수 있는 수를 더해주어야 한다. 

 

4. 그렇기 때문에 누적합계가 S보다 커지기 직전까지 더했던 수가 정답이다. 

 

---

 

#include <iostream>

using namespace std;

int main(int argc, const char * argv[])
{
    long long S; //오버플로 방지용 
    cin >> S;
    
    int N = 0;
    long long sum = 0;
    while (S > sum)
    {
        sum += ++N;
        
        if (S < sum)
            N--; //누적합계가 S보다 커지면 지금 N의 직전에 더했던 수가 최댓값이기 때문에 1뺀 후 반복문 종료
    }
    
    cout << N;
    
    return 0;
}