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

 

 

오늘은 이진탐색으로 풀 수 있는 문제를 가져왔다.

 

 

문제 1789번

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

1789번: 수들의 합

 

이진탐색을 하려면 정렬은 필수인데 여기서는 정렬된 자연수를 생각하므로 따로 정렬은 필요없다.

start와 end를 각각 1과 S로 잡고 그 사이의 값을 mid로 잡는다. while문을 이용하여 start<=end일때까지 계속 반복해준다. 1부터 mid까지의 숫자들을 모두 더했을 때 S보다 작거나 같으면 result에 해당 숫자들 중 가장 큰 mid를 넣어주고 start에는 mid+1을 넣어준다. 만약 반대의 경우라면 범위를 작게 만들 필요가 있기 때문에 end에 mid-1을 넣어준다.

 

#include <iostream>
using namespace std;

int main() {
	long S;
	cin >> S;
	
	long start = 1;
	long end = S;

	long result=0;

	while (start <= end) {
		long mid = (start + end) / 2;
		if ((mid + 1)*mid / 2 <= S) {
			result = mid;
            		start = mid + 1;
		} else {
			end = mid - 1;
		}
	}
	cout << result;
}