[BOJ/C++] #1789번: 수들의 합

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

1789번: 수들의 합

 

 

 

문제

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

 

입력

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

 

출력

첫째 줄에 자연수 N의 최댓값을 출력한다.

 

예제 입력 1 

200

예제 출력 1 

19

 

 

풀이

탐욕법을 이용하면 쉽게 풀 수 있다. 

N이 최대가 되기 위해선 작은 수부터 더해야 함을 알아야 한다.

* int형이 나타낼 수 있는 최대 숫자와 문제가 주는 최대 범위가 맞는지 꼭 확인할 것.

 

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


long long solution(long long);


int main(void)
{
	// 입력 받기
	long long case_num;
	cin >> case_num;
	cin.ignore();
	
	// 입력 받고 함수 적용
	cout << solution(case_num);
	return 0;
}


long long solution(long long number)
{
	long long count = 0;
	long long i = 1;
    
	while (i < number-i)
	{
		number -= i;
		count += 1;
		i += 1;
	}
	count += 1;
	return count;
}