[알고리즘] 백준 > #2003. 수들의 합2

문제링크

백준 #2003. 수들의 합2

풀이방법

문제가 전에 풀었던 백준 > #11659. 구간 합 구하기4와 비슷하죠? 근데 같은 부분합 배열 방식으로 문제를 해결하면 시간초과가 발생합니다. (O(n + n^2) -> 시간 제합 0.5를 쉽게 넘기 때문)

따라서, 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해 해결하는 테크닉인 투포인터를 사용해 해결했습니다!

변수들을 다음과 같이 사용했습니다.

• start: 구간 내 가장 앞의 원소를 가리킴
• end: 구간의 마지막 원소 뒤를 가리킴

따라서, 구간을 [start, end)로 설정했습니다~

코드

import java.util.Scanner;

public class SumOfNumbers {
    static int[] array;
    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        array = new int[n + 1]; // end는 포함 되지 않아서 0 ~ (n-1)까지 값을 넣고 n은 더미로 넣어둠
        for (int i = 0; i < n; i++) array[i] = sc.nextInt();

        int start = 0;
        int end = 0;
        int sum = 0;

        int result = 0;

        while ((start <= end) && (end <= n)) {
            if (sum == m) result++;

            if (sum >= m) sum -= array[start++];
            else sum += array[end++];
        }

        System.out.print(result);
    }
}