[BOJ] 백준 1789번 수들의 합 (Java)

#1789 수들의 합

난이도 : 실버 5

유형 : 그리디

1789번: 수들의 합

▸ 문제

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

그리디 알고리즘은 현재 주어진 상황에서 가장 이득이 되는 최선의 경우를 선택하는 알고리즘이다. 따라서 이는 최적해를 구하는 것이 아니기 때문에 현재의 선택이 뒤에 연산에 어떤 영향을 끼칠지 고려하지 않는다.

 

자연수의 합 S이 있을 때 a1 + a2 + a3 + ... +an 총 N개의 자연수의 합으로 이루어져있다. N의 최댓값을 구하기 위해서는 a(1...n)의 값들을 가장 작은 자연수들이 가장 많이 들어가게 하면 된다.

 

Sum(1..n-1) <=  S <= Sum(1..n)가 성립하는 N의 값을 구할 때 까지 자연수의 최솟값인 1부터 대입하여 넣어주도록하자. 왜냐하면 마지막 값 X를 n, n-1의 사이값으로 대체하면 결국 자연수들의 합은 1 + 2 + 3 + ... + n-2 + X = S로 가장 작은 자연수들로 이루어진 합이 되기 때문이다. 

 

• S  = Sum(1..n-2) + X ( n-1 <= X <=n)

 

결국 n-2번까지 그리디하게 현재 가능한 가장 작은 자연수 값을 선택하는 것이다. 만약 1...n-2에 있는 자연수를 n-2보다 더 큰 수로 대체하게 된다면 최적해 N보다 같거나 큰 값이 나오므로 해당 방식이 최적해임을 증명할 수 있다. 

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long n = Long.parseLong(br.readLine());
		
		long sum =0;
		int idx=1;
		while(true) {
			sum = (long)Math.pow(idx, 2)+idx;
			if(sum >2*n) break;
			idx++;
		}
		
		System.out.println(idx-1);
	}
}