[백준] 1789 - 수들의 합

[백준] 1789번 - 수들의 합

[링크] https://www.acmicpc.net/problem/1789

💎 문제 조건과 설명

문제 조건과 설명은 위의 링크를 참조 부탁드립니다.

🚀 생각한 아이디어

• 서로 다른 N개의 자연수의 합이 S가 되어야 하고, 그 N개의 최댓값을 구해야 합니다.
• 즉 서로 다른 최대한 많은 자연수들을 골라서 합이 S가 되게 하려면, 1부터 하나씩 증가시키면서 더해가면 됩니다.
• 1+2+3+4+5+… = S 이런 식으로 하면 서로 다른 자연수들을 최대한 많이 고르는 것입니다.
• 예를 들어 200 을 만들기 위해 계속 더해 보았습니다.
  • 1+2+3+…+19 = 190 이고, 1+2+3+…+20 = 210 입니다.
  • 1+2+3+…+17+18+19 가 아니라 1+2+3+…+17+18+29 로 바꾸면 200을 만들 수 있으며 더한 숫자의 갯수는 19개입니다.
  • 즉, 1부터 계속 더해나가면서 더한 자연수의 갯수를 같이 카운트하고, 더해간 합이 S를 처음으로 초과할 경우 현재까지 더한 자연수의 갯수에서 -1 한 것이 정답입니다.
  • 위의 예시를 다시 보면, 1부터 계속 더해나가서 20까지 더해나갔을 경우 값은 210이며, 총 숫자는 20개 더했습니다. 200을 초과했으므로, 정답은 20 - 1 = 19개입니다. 숫자 19개를 더한 결과인 190에서 맨 마지막 19를 29로 바꾸면 200을 만들 수 있기 때문입니다.
  • 그러므로 간단하게 말하면 1부터 차례대로 더하다가 값이 초과되면, 현재까지 더한 숫자의 갯수-1 이 정답입니다.

📜 소스코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>

using namespace std;

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	long long S;
	cin >> S;

	long long sum = 0, num = 1;
	int cnt = 0;

	while (1) {
		sum = sum + num;
		cnt++;
		if (sum > S) {
			cnt--;
			break;
		}
		num++;
	}

	cout << cnt;
	return 0;
}