백준 1789번 <수들의 합>

백준 알고리즘 1789번

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

1789번: 수들의 합

---

1789번

서로 다른 N개의 자연수의 합으로 S를 만들 수 있다. S를 알고 있을 때, N의 최댓값을 얼마일지 구하여라.

 

입력으로 첫 줄에 자연수 S가 주어진다. 

 

출력으로 자연수 N의 최댓값을 출력한다.

---

문제 해결

입력으로 들어오는 S가 최대 42억,,, 이니까 long형을 써야 한다.

 

최대의 개수를 구하는 것이기 때문에 최대한 작은 수들로 합을 구성해야 한다.

따라서 1부터 시작해서 더할 수 있다면 더한다. -> 그리디 알고리즘

S에서 idx를 뺀 값이 idx+1보다 작다면 더할 수 없다. 왜냐하면 더 작은 수는 이미 더해졌기 때문이다. 이럴 때는 idx보다 더 큰 수를 더해야 한다. S가 0이 된다면 break 하면 된다.

 

---

코드

package bj1789;

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 s = Long.parseLong(br.readLine());
		long cnt = 0;
		long idx = 0;
		while (true) {
			idx++;
			long temp = s - idx;
			if (temp == 0) {
				cnt++;
				break;
			} else if (temp < idx + 1) {
				continue;
			}
			s -= idx;
			cnt++;
			if (s == 0) {
				break;
			}
		}
		System.out.println(cnt);

	}

}

---

결과

 

---