백준 1789 수들의 합 c++ (이분 탐색)

문제 출처 : https://www.acmicpc.net/problem/1789

1789번: 수들의 합

문제

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

입력

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

출력

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

알고리즘 분류

• 수학
• 그리디 알고리즘

풀이

서로 다른 N개의 수로 S를 만드는 방법 중 N이 최대가 되는 방법은,

S가 11이라고 하면,

1 + 2 + 3 + 4 =10이고, 1 + 2 + 3 + 4 + 5 = 는 15이기 때문에,

1 + 2 + 3 + 5 =11로 즉 4이다.

N이 최대여야 하기 때문에, 낮은 수부터 더해가며, 더한 값들이 S를 넘기기 직전에, 마지막으로 더하는 수를 조정하면 S를 만들 수 있다.

이를 이용한 풀이로, 그냥 선형 알고리즘으로 1부터 쭉 더해가도 되지만,

1부터 n까지의 합은 n(n+1)/2인 점과, 리스트가 오름차순이라는 점을 이용해

이분 탐색으로 풀 수도 있다.

아래는 이분 탐색 풀이이다.

start = 1부터 end = S까지의 범위에서, mid값을 구하고,

mid까지의 합인 result = mid*(mid+1)/2가 S보다 작다면,

start = mid+1, end = end

mid까지의 합인 result가 S보다 크다면,

start = start, end = mid

위처럼 이분 탐색을 진행하여, 마지막으로 반환되는 mid값이 N이 된다.

 

코드

#include <iostream>

using namespace std;

long long n;
long long answer;
void biSearch(long long start, long long end) {
	
	if (start >= end) {
		return;
	}
	long long mid = (start + end) / 2;
	long long result = mid * (mid + 1) / 2;
	
	if (result <= n) {
		answer= mid;
		biSearch(mid + 1, end);
	}
	else {
		biSearch(start, mid);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	 biSearch(1, n);
	 cout << answer;
	 return 0;
}