문제

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

풀이

S를 만들기 위해 더하는 수들의 간격이 작을수록 개수 n이 커진다. 따라서 n의 최댓값을 구하려면 1 + 2 + ... + n 이런 식으로 수들의 간격을 최솟값 1로 하고 그 합이 S에 가까워지도록 한다. 1씩 늘려가며 합을 구하다가 S를 넘었을 때, 더한 수들의 개수를 출력하면 그게 곧 n의 최댓값이 된다.

S = 200일 때를 생각하면, 1 + 2 + ... + 19 = 190 인데 여기서 한 개의 숫자에 10을 더하면 합이 S가 된다. 예를 들어 19에 10을 더하면 1 + 2 + ... + 18 + 29 = 200 이렇게 합이 200이 되면서도 그 수들의 개수가 최대가 된다. (단, 10을 더했을 때 그 수가 기존에 이미 더했던 숫자면 안 된다. n개의 수는 서로 달라야 하므로)

#include <iostream> 
#include <vector> 
#include <string>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

	long long S; 
	cin >> S; 

	long long sum = 0; // 데이터 범위 잘 확인하기!!! 
	int n = 1; // 더하는 수 자체 
	int cnt = 0; // 더한 개수 
	
	while(sum < S){ 
		sum += n; 

		if(sum > S) break; 
		
		cnt++; 
		n += 1; 
	}

	cout << cnt; 
	
	return 0;
}

알고리즘은 맞았는데,, 데이터 범위를 제대로 확인하지 않아서 틀렸다. 자연수 S (1 ≤ S ≤ 4,294,967,295)의 범위는 int를 넘어서기 때문에 long long 으로 선언해야 한다. (int는 최대 약 21억)