[백준] 1789번 - 수들의 합 / C++

문제

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

 

입력

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

 

출력

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

 

코드

#include <iostream>

using namespace std;

long long S;

int main()
{
	long long s, m, e;
	long long n, sum;

	cin >> S;
	s = 1;
	e = S;
	while (s <= e)
	{
		m = (s + e) / 2;
		sum = m * (m + 1) / 2;
		if (sum <= S)
		{
			n = m;
			s = m + 1;
		}
		else
		{
			e = m - 1;
		}	
	}
	cout << n << endl;
	return 0;
}

 

S를 만들기 위한 서로 다른 자연수의 최대 개수를 구하려면 작은 수들을 최대한으로 사용해야 한다. 따라서 1부터 n까지의 합이 S를 넘지 않는 n의 최댓값을 구하면 된다. 이분 탐색을 통해 n의 값을 찾을 수 있다.

 

링크

1789번: 수들의 합

inbdni/Baekjoon