[백준 2003번] 수들의 합 2

원본 링크

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

Intro

이번 문제는 두 개의 포인터를 이용해서 푸는 문제이다.
뭐 가령 퀵 정렬과 같이 두 개의 포인터가 왔다갔다 하면서 값을 조정하고 계산한다고 보면 된다.
문제는 단순하지만 처음 접해보면 어렵다고 느낄 수 있는 문제였다.

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

예제

예제 입력 1

4 2
1 1 1 1

예제 출력 1

3

예제 입력 2

10 5
1 2 3 4 2 5 3 1 1 2

예제 출력 2

3

주 알고리즘 분류

• 두 포인터

나만의 풀이

이 문제에서는 퀵 정렬을 구현하듯 2개의 (인덱스) 포인터를 써서 해결해야 제한조건 내에 풀 수 있다.
보면 알겠지만 데이터 수가 최대 10000개까지 주어지니, 단순히 생각하면, C(10000, 1) ~ C(10000, 10000)까지 고려해야 한다.
이와 같은 브루트포스 방식은 효율이 별로 안 좋으니, 포인터를 써서 구현할 생각이다.

먼저 기본적인 값을 적절히 받아주자. (입력값을)
이후 나는 수열의 개수, 누적 합, 포인터 1, 포인터 2에 해당하는 변수를 선언했다.
각각 cnt, sums, i, j로 설정했다.
참고로 초깃값은 0, 입력 데이터의 첫 번째 원소, 0, 0이다.

while j < n:
    if sums < m:
        j += 1
        if j < n: sums += a[j]
    elif sums > m:
        sums -= a[i]
        i += 1
    else:  # sums == m
        cnt += 1
        sums -= a[i]
        i += 1
        j += 1
        if j < n: sums += a[j]

위 코드는 포인터를 조정하고 합계를 구하는 핵심 부분이다.
i는 부분 수열의 시작 위치를 의미하며, j는 끝 위치를 의미한다.
따라서 일단 j < n인 경우에 한해서 while문을 돌도록 결정한다.

일단 현재까지의 sums가 우리가 목표하는 m값보다 작으면, j를 증가시키고 sums에다가 a[j]값을 저장한다.
반대로 sums가 m값보다 큰 경우, sums에서 a[i]를 빼고, i를 1 증가한다.
그리고 만일 sums == m인 경우, 목표하는 수열이므로 cnt값을 1 증가시킨다.
그리고 순차적으로 a[i] 빼기 > i 증가 > j 증가 > a[j] 추가를 수행한다.

최종적으로 cnt값을 마지막에 출력하면 원하는 수열의 개수를 얻을 수 있다.

최종 코드는 다음과 같이 만들어졌다.

n, m = map(int, input().split())
a = list(map(int, input().split()))
cnt, sums, i, j = 0, a[0], 0, 0

while j < n:
    if sums < m:
        j += 1
        if j < n: sums += a[j]
    elif sums > m:
        sums -= a[i]
        i += 1
    else:  # sums == m
        cnt += 1
        sums -= a[i]
        i += 1
        j += 1
        if j < n: sums += a[j]

print(cnt)

마치면서

사실 앞선 두 개의 포인터를 활용하는 예시로 퀵 정렬을 들긴 했지만, 위 코드와는 조금 다르게 동작된다.
(퀵 정렬은 양쪽에서 중앙으로 포인터들이 접근한다.)
아무튼, 이렇게 두 개의 포인터를 활용해서 문제를 효과적으로 풀 수 있다는 점이 인상 깊었다.
두 포인터를 사용하는 문제는 그닥 많지 않지만, 그래도 기본 활용 형태 정도는 알아놓으면 좋겠다 생각한다.