[JAVA] 백준 2018 투포인터

2018번: 수들의 합 5

문제

주어진 수에 대해서 연속된 자연수의 합으로 나타낼 수 있는 경우의 수를 출력하라.

풀이

주어진 수가 15일 때, 경우의 수는 다음과 같다.

1+2+3+4+5, 4+5+6, 7+8, 15

모든 수들은 자기 자신을 가지고 시작한다.

투포인터를 사용하면 쉽게 풀 수 있다.

두개의 포인터 i, j가 있을 때

i, j를 1부터 시작하여 두 점의 구간의 합을 구해나간다.

만약 구간의 합이 주어진 수 N보다 작다면 j를 높이고 주어진 수보다 크다면 i를 빼면서 올라간다.

만약 주어진 값과 같다면 i와 j 모두 움직인다.

즉, 다음과 같이 움직인다.

1 + 2 = 3 (3 < N)

1 + 2 + 3 = 6 (6 < N)

1 + 2 + 3 + 4 = 10 (10 < N)

1 + 2 + 3 + 4 + 5 = 15 (15 = N)

2 + 3 + 4 + 5 + 6 = 20 (20 > N)

3 + 4 + 5 + 6 = 18 (18 > N)

4 + 5 + 6 = 15 (15 = N)

다음과 같이 구간이 움직인다.

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int start = 1;
        int end = 2;
        // N이 되는 경우의 수를 미리 선택
        int answer = 1;
        int sum = start + end;
        while(end < N){
            if(sum < N) sum += ++end;
            else if(sum > N) sum -= start++;
            else{
                sum += ++end;
                sum -= start++;
                answer++;
            }

        }
        System.out.println(answer);
    }
}

결과