C++ / 1789 / 수 들의 합 ( 그리디 알고리즘 )

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

문제 요약

서로 다른 n개의 수의 합이 s 라고 할 때 n의  최댓값을 구해야 합니다.

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어집니다.

 

문제풀이

1. s를 입력받아 n을 구해야하기 때문에 long long int로 값을 입력 받습니다.

2. s가 200 일때 1 + 2 + 3 ... 18 + 19 = 190 ( 1부터 19 까지 더하면 )입니다. 여기서 20을 더하면 210이 돼서 200을 넘어가게 되는데 마지막에 20을 더하는것이 아닌 19를 더해야 할 때 모자란 10만큼 더 29를 더하면 19번째에 200이 완성됩니다.

3.반복 문을 통해 200을 넘을때 까지 sum에 i를 1부터 더합니다. 

4. p도 매 횟수마다 + 1 해줍니다.

5. sum이 200을 넘어가면 break로 멈춰주고 p에 -1을 더해주고 ( 목표 횟 수 보다 한개 더 더해졌으니 빼줘야 합니다. )출력합니다.

 

주의 할 점

이번 문제도 int의 크기를 넘어가 우려가 있기 때문에 long long int를 사용하는 것이 중요한 것 같습니다.

 

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

long long int s, p = 0, sum = 0, sum2 = 0;

int  main()
{

	cin >> s;

	if (s <= 0)
	{
		return 0;
	}


	for (long long int i = 1; i <= s; i++)
	{
		// 더해진 횟수
		p++;
		// 1 + 2 + 3 +...
		sum += i;
		if (sum > s)
		{
			// 목표 숫자를 넘어갔으니 - 1
			p -= 1;
			break;
		}
	}
	cout << p;
	return  0;
}

반응형

예제

200

결과