[백준] Greedy: 수들의 합

문제

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

입력

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

 

문제 접근

• 어떤 수가 주어졌을 때, 서로 다른 수들의 합이 가장 작은 경우는 1부터 차례대로 더했을 경우이다.
• 그러면 최소 개수를 어떻게 판단할까? 핵심은 서로 다른 수를 반환하는 것이 아닌,
• 단순히 서로 다른 수의 개수를 반환하는 것이다.
• 수에 따라 1부터 차례대로 더했을 때 S와 일치하는 경우도 있고 그렇지 않은 경우가 있다.
• 합일 일치할 경우는 수를 하나 씩 늘렸을 대 합이 일치하는 자연수를 반환하면 된다.
• 하지만 1~n까지의 합이 S가 안나오면 어떻게 할까?
• 다음과 같이 상당히 애매한 숫자인 29가 주어졌다고 해보자.
• 1부터 차례대로 더하다 보면 7을 더할 때 28이 되고, 다음 수인 8을 더하면 28+8 = 36이 된다.
• 이런 경우는 S를 초과한다. 그렇다면 합을 S인 29와 일치시키려면 어떻게 할까?
• 7번째 수인 7을 건너뛰고 8을 더하면 된다.
• 즉, 넘어가기 직전의 수를 S와 일치시킬 수 있는 수로 바꾼다고 생각하면 된다.
• 따라서 반환해야 할 서로다른 자연수의 개수는 넘어가기 직전의 수라고 생각하면 된다.
• 개수만 생각하기에 가능한 문제이다.

그렇다면 위의 경우에는 1, 2, 3, 4, 5, 6, 8을 더하고 합이 29가 된다.

작은 수부터 더했기 때문에 서로 다른 수의 개수가 가장 큰 경우가 보장된다.

그렇다면 예제로 주어진 200의 경우에서도 확인해 보자.

 

이를 코드로 구현하면 다음과 같다.

 

풀이 코드

현재까지의 합이 S를 초과하는 경우 루프를 나오게 되며 그 때의 자연수에서 1을 빼준다.

package baekjun;

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

public class _1789 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long S = Long.parseLong(br.readLine()); //서로 다른 N개의 자연수의 합.

        long sum=0;
        long i=0;
        while(sum <= S){
            i++;
            sum += i;
        }

        System.out.println(i-1);
    }
}