백준/그리디

[백준] C++ 1789(수들의 합)

2zreal 2024. 7. 5. 02:51

 

#include <iostream>

using namespace std;

int main(void)
{
	long long int a=0;
	
	cin>>a;
	
	int count=0;
	long long int sum=0;
	long long int i=1;
	
	while(true)
	{
		if(a-(sum+i)<=i)
		{
			count++;
			break;
		}
		sum=sum+i;
		i++;
		count++;
	}
	
	cout<<count;
	
	return 0;
}

 

이 문제는 서로 다른 N개의 자연수의 합이 S일 때 자연수 N의 최댓값을 구하는 문제이다.

S는 입력으로 주어진다.

S가 7이 입력되었다고 생각해 보자. 그러면 1+2+4(3개)가 된다. 서로 다른 자연수의 개수는 3개이다.

7-(3+3)<=3 여기서 걸려서 while문을 빠져나온다.

 

이 문제에서 입력값의 범위는 S(1 ≤ S ≤ 4,294,967,295)이다. if(a-(sum+i)<=i) 여기서 int값의 범위를 넘어 버릴 수 있기 때문에 long long int로 선언해 주어야 한다.