[Java] 백준 1789 - 수들의 합

Baekjoon_1789 - 수들의 합

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

문제

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

입력

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

출력

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

---

해결방법

• S보다 작거나 같은 1~k의 합에서 k가 최댓값이다.
• 물론 S가 연속된 자연수의 합으로 딱 떨어진다는 보장은 없지만 아래의 경우를 보자.
  • 만약 S가 14라면 1~4 까지의 합인 10이 연속된 자연수 합의 최댓값이다. 여기서 그냥 1, 2, 3, 4 를 1, 2, 3, 8 이라고 가정해버리면 되는 것이다. 어차피 개수는 같기 때문이다.
  • 만약 S가 15라면 1~5 까지의 합이 15이기 때문에 답은 5가 된다.
• 따라서 어떠한 경우든 간에 S보다 작거나 같은 1~k의 합에서 k가 최댓값이다. 라는 명제가 참이 되는 것이다.
• S의 범위에 주의하자! 주어진 S의 범위는 int의 범위를 벗어나기 때문에 long 타입으로 계산해야 한다.

코드

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

public class Baekjoon_1789 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());

        System.out.println(getMaxK(n));
    }

    public static int getMaxK(long targetNum){
        long sum = 0;
        int cnt = 0;

        while(true){
            if(sum + cnt+1 > targetNum){
                break;
            }
            sum += cnt+1;
            cnt ++;
        }

        return cnt;
    }
}