[백준 1789번] 수들의 합

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

---

문제

---

아이디어

고려해야 할 점

• S의 조건 (1 <= S <= 4,294,967,295) 이므로 int 의 범위를 벗어남. -> Long 사용

N의 최댓값이라 하면 결국 1부터 2, 3, ... 차례대로 자연수를 더하는게 가장 많은 자연수를 사용한 결과이다.

 

따라서

• N = 1 : 1, 2
• N = 2 : 3(1+2), 4(1+3), 5(2+3)
• N = 3 : 6(1+2+3), ...
• N = 4 : 10(1+2+3+4), ...

N이 커지는 경우는 1씩 높여가며 숫자를 더해줄 때 커진다. (1+2+3+4+5+...)

 

N x (N+1) / 2 보다 작은 수들은 N-1의 최대값을 가진다.

---

전체 코드

package Baekjoon;

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

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

        int count = 0;
        while(true) {
            count++;
            S -= count;
            if(S == 0) {
                System.out.println(count);
                break;
            }
            else if(S < 0) {
                System.out.println(count-1);
                break;
            }
        }
    }
}