[ 백준 2003번 ] 수들의 합2

1. 문제

2003번: 수들의 합 2

 

2. 풀이

해당 문제를 요약하자면 주어진 수열에서 연속된 부분수열의 합이 C를 만족하는 경우의 수를 찾으라는 내용이다.

 

가장 단편적인 방법으로는 brute-force로 해당 문제를 해결해도 될 것으로 보인다. 하지만 연속된 부분수열의 합을 매번 구해야 한다면 O(N²)의 시간복잡도가 발생할 것이다. 그렇다면 부분 수열의 합을 어떻게 하면 효율적으로 계산할 수 있을까를 먼저 해결해보자.

 

1.1 누적합

연속된 부분 수열의 합을 구할 때는 누적합을 이용하는 것이 가장 효과적이다. 누적합의 원리는 간단한데, 입력 받은 수열을 각 요소들의 합으로 미리 저장해 두는 것이다. 입력이 아래와 같이 주어졌을 때를 가정해보자.

• a[1] = 2
• a[2] = 1
• a[3] = 4

 

(2, 3) 부분 수열의 합을 구한다고 가정했을 때, a[2]+ a[3] 으로 구할 수도 있지만 이는 이중 for문을 돌려서 구해야 한다. 하지만 누적합을 아래와 같이 저장해둔다면 어떨까

• dp[1] = 2
• dp[2] = 3
• dp[3] = 7

 

a[2] + a[3] = a[1] + a[2] + a[3] - a[1] = dp[3] - dp[1]로 해결할 수 있다.

 

1.2 투-포인터(two pointer)

누적합을 구했다면, 부분 수열을 만들어서 합이 C와 일치하는가를 살펴봐야 한다. 부분수열의 합을 만드는 가장 단편적인 방법은 아래와 같이 이중 for문으로 해결하는 것이다.

int cnt = 0;
for (int i = 1; i <= N; i++) {
    if (arr[i] < C) continue;
    for (int j = 0; j < i; j++) {
        if (arr[i] - arr[j] == C) {
            cnt++;
        }
    }
}

 

하지만 이 방법은 여전히 O(N²) 시간 복잡도가 발생한다. 여기서 한 가지 중요한 키워드를 생각해볼 수 있는데, 우리는 누적합의 배열은 항상 dp[N - 1] <= dp[N] 임을 알 수 있다. 따라서 두 개의 포인터 변수를 이용해 범위를 조금씩 우측으로 옮겨가며 부분수열의 합을 체크해주면 O(N)에 해결할 수 있게 된다.

 

투-포인터 알고리즘의 세부 설명은 별도의 블로그 게시글을 통해서 기재하겠다. 하지만 향후 게시글에서도 설명하겠지만 해당 투-포인터 알고리즘이 잘 이해되지 않는다면 애벌레의 움직임을 생각해본다면 쉽게 와닿을 것이다!

 

이미지 출처: https://kissimmee.tistory.com/388

 

3. 소스코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        long C = Long.parseLong(st.nextToken());

        long[] arr = new long[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = arr[i - 1] + Long.parseLong(st.nextToken());
        }

        int cnt = 0;
        
        // 투-포인터
        int start = 0;
        int end = 1;
        do {
            long diff = arr[end] - arr[start];
            if (diff == C) cnt++;

            if (diff >= C) start++;
            else end++;

            if (start == end) end++;
        } while (end <= N);

        bw.write(cnt + "");
        bw.close();
        br.close();
    }
}

 

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code