백준 2018 자바

 

투 포인터 문제이다.

이런 식으로 start pointer, end pointer 2개의 포인터를 조정하며 수들의 합이 N이 되면 count를 +1해준다.

두 포인터 문제에서는 sum < N, sum > N, sum == N 3가지 경우를 잘 분리해서 코드를 작성해야 한다.

(N이 15라 가정)

1. sum < N

만약 start pointer가 1이고 end pointer가 3이면 sum = 1+2+3 = 6이 된다.

그렇다면 sum은 N보다 작기 때문에 end pointer를 하나 올려서 sum을 더 크게 만들어야 한다.

sum < N 이면 end pointer++;

그러면 end pointer는 4가 될 것이고 

다음 sum은 1+2+3에서 4를 추가로 더해줘야 한다.

sum < N이면 end pointer++, sum = sum + end pointer;

 

2. sum > N

start pointer = 1, end pointer = 6이라고 가정하면

sum = 1+2+3+4+5+6 = 21  > N(15)가 된다.

그렇다면 우리는 sum을 줄여야 한다. 이 때는 start pointer를 오른쪽을 한 칸 올리면 된다. 

sum > N이면 start pointer++;

그리고 sum은 sum = sum - start pointer로 조정한다.

3. sum == N

cnt를 ++ 시키고

end pointer를 ++ 시킨다. 새로운 sum을 또 찾아야 하고 end pointer가 N까지 가야 반복문이 끝나기 때문이다.

 

 

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int cnt = 1;
        int start_idx = 1;
        int end_idx = 1;
        int sum = 1;

        while (end_idx != N) {

            if (sum == N) {
                cnt++;
                end_idx++;
                sum = sum + end_idx;
            } else if (sum > N) {
                sum = sum - start_idx;
                start_idx++;
            } else {
                end_idx++;
                sum = sum + end_idx;
            }
        }
        System.out.println(cnt);

    }
}