[백준/Java] 1789번 - 수들의 합

🙂 문제

1789번 : 수들의 합

✏️ 접근방법

서로 다른 수의 합이라고 했기 때문에

200 = 199 + 1
	= 198 + 2 
    = 197 + + 2 + 1 
    = 196 + 3 + 1 
    = ...

이런 식으로 수의 합을 만드는 경우들을 바로 떠올렸다. 하지만 이 문제에서는 최대 개수를 묻고 있기 때문에 그냥 단순히 서로 다른 수의 합을 생각하는 것이 아니라 많은 수를 더해야 한다는 것에 생각해야 한다.

👉 서로 다른 자연수 N개의 합인데 N이 최대라면 가장 간단한 방법은 작은 수부터 연속적으로 더해나가는 것이다.

---

💡풀이

예를 들어, S = 15인 경우에는 아래와 같이 합을 나타낼 수 있고 N = 5이다.

1 + 2 + 3 + 4 + 5 = 15

S = 14라면 위의 식에서 1을 빼면 되니까 N = 4이다. 마찬가지로, S = 10이면 위의 식에서 5를 빼면 되기 때문에 N = 4이다. S가 9이면 6을 빼줘야 하는데 6이 없기 때문에 1과 5를 빼줘야 하므로 N = 3이 된다.

식을 만들기 쉽게 예시를 들어보면 아래와 같다.

S = 20 이라고 하자.
21 = 1 + 2 + 3 + 4 + 5 + 6 -> N = 6이지만 (21 - 20) 인 1이 식에 존재한다. 따라서 N = 6 - 1 = 5이다.

필요한 값은 sum(차례대로 더해지는 값의 결과) , n(찾고자 하는 값(합으로 만들어져야 하는 수)), cnt(숫자 개수)

✨
1) 찾으려는 값보다 커질때까지 1부터 차례로 더하면서 count한다. (cnt++)
2) sum의 값이 처음에 입력받은 수인 n보다 커지면 반복문을 빠져나와야 한다.
3) count - 1을 해서 더한 숫자의 개수를 구한다.

---

💻 답안

import java.io.*;

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;
        long cnt = 0;

        while (true) {
            if (sum > n) {
                break;
            }
            sum += cnt + 1;
            cnt++;
        }
        
        System.out.println(cnt - 1);
    }
}