[BOJ 그리디] 수들의 합 1789.JAVA

문제 링크 : https://www.acmicpc.net/problem/1789
문제 등급 : Silver V

1789번: 수들의 합

문제 해결 로직

1. 찾고자 하는 값보다 클 때까지 1부터 n까지 더하면서 count 한다.
2. count - 1을 하여 더한 개수를 구한다.
   1. n이 20일 때, 1, 2, 3, 4, 5, 6으로 21을 구한다.
   2. count는 6이 된다.
   3. 하지만 n과 21은 다르기 때문에 하나의 값을 빼주어야 하는데 n과 21의 차가 더한 값에 있음으로 count에서 1을 빼준다.

이 문제를 보고 백트래킹으로 문제를 풀려고 하였다. 하지만 너무 깊게 생각했다.

너무 오랜 시간 붙잡고 있어도 오기일뿐 효율이 안 나기 때문에 문제의 풀이를 보았다.

문제의 풀이를 보고 무릎을 탁 쳤다.

전혀 생각해보지 못한 풀이였다.

 

아래와 같이 소스를 공유합니다.

public class 수들의 합 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long n = sc.nextLong();
        long sum = 0, cnt = 0;
        for (int i = 1; i <= n; i++) {
            if(sum > n) break;
            sum += i;
            cnt++;
        }

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