[백준 Java] 1789 수들의 합

문제링크

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

풀이

합이 S라면 1부터 N까지 더하며 S가 넘지 않을때까지 반복한다.

input은 S(1 ≤ S ≤ 4,294,967,295)으로 40억이 넘어가기 때문에 long으로 사용해야 한다.

1부터 더해야 하기 때문에 idx를 1로 시작한다.

 

200을 예로 들었을 때, 아래의 코드는 sum = 210, idx = 21인 상태에서 if문에 걸리게 된다.

idx++이 된 부분에 대해서 한번 빼주고, sum이 초과되는 부분에서 한번 더 빼준다.

설명으로 하니 복잡한데 반복문 내에 idx와 sum을 찍어보면 아래와 같이 나온다.

//idx sum
1 1
2 3
3 6
...
19 190
20 210
나가!
19

후위연산자로 증가한 값을 하나 줄여주고, 반복문 내에서 sum이 초과한 이전의 숫자를 사용하기 위해 한번 더 빼준다.

따라서 idx를 -2 해주게 되는 것이다.

처음에 이것을 잡는데 시간이 오래 걸렸다.

 

그 외의 반례로는 input 1, output 1을 확인하기.

 

코드

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

public class Main{

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

        //1부터 계속 더하면서 S가 넘지 않을때까지 반복
        long sum = 0;
        long idx = 1;
        while(true){
        	//System.out.print(idx +" ");
            sum += idx++;
            //System.out.println(sum);
            if(sum > S){
                //System.out.println("나가!");
                idx-=2;
                break;
            }
        }
        System.out.println(idx);
    }
}

그리디는 항상 접근이 어렵고 감을 잡으면 풀이는 쉬워지는 것 같다.

더 많이 풀어봐야지