백준 2003번 - 수들의 합 2

2003번 수들의 합2

문제

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을 넘지 않는 자연수이다.

출력

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

 

문제해설

이번 문제는 합이 m이되는 부분배열의 개수를 구하는 문제이다.

 

슬라이딩 윈도우 기법과 투포인터 접근법을 사용하여, 

배열을 효율적으로 순회하며 매번 합을 다시 계산하지 않고도 문제를 해결할 수 있다.

 

슬라이딩 윈도우를 알기 위해선, 투포인터에 대한 간략한 이해가 필요하다.

 

슬라이딩 윈도우는 연속적인 부분 배열이나 구간을 다룰 때 주로 사용된다. 

창의 크기를 확장하거나 축소하면서 해결하는 방식이다. 

 

반면, 투포인터 기법은 정렬된 배열에서 특정 조건을 만족하는 쌍을 찾거나,

양쪽 끝에서 중앙으로 이동하면서 문제를 해결할 때 사용된다.

 

두 기법 모두 두 개의 포인터를 사용하지만, 슬라이딩 윈도우는 항상 연속된 구간을 유지한다는 점에서 차이가 있다.

 

작성한 코드의 슈도코드를 정리하면 아래와 같다.

 

슈도코드

1. 입력 처리: 첫 번째 줄에서 배열의 크기 n과 목표 합 m을 입력받고, 두 번째 줄에서 배열 요소들을 입력받는다.
2. 초기화: cnt는 목표 합을 가지는 부분 배열의 개수를 추적하며, left는 슬라이딩 윈도우의 시작점을 나타내고, current_sum은 현재 창의 합을 저장한다.
3. 슬라이딩 윈도우 루프:
   • for right in range(n) 루프는 오른쪽 포인터를 배열의 끝까지 이동시키며 창을 확장한다.
   • arr[right]를 current_sum에 더해 현재 창에 새로운 요소를 포함시킨다.
4. 창 조정:
   • current_sum이 m을 초과하면, left 포인터를 오른쪽으로 이동시키며 창을 줄이고, 그에 따라 arr[left] 값을 current_sum에서 뺀다.
   • 이 과정은 current_sum이 m 이하가 될 때까지 반복된다.
5. 합이 목표 값과 일치하는지 확인:
   • current_sum이 m과 같으면, cnt를 1 증가시켜 유효한 부분 배열을 찾았음을 기록한다.
6. 출력: 최종적으로 cnt 값을 출력하여 목표 합을 가지는 연속적인 부분 배열의 개수를 반환한다.

 

정답코드

n, m = map(int, input().split())
arr = [int(i) for i in input().split()]

cnt = 0
left = 0
current_sum = 0

# 슬라이딩 윈도우
for right in range(n):
    current_sum += arr[right]

    # 현재 합이 m을 초과하면 왼쪽에서 창을 줄임
    while current_sum > m and left <= right:
        current_sum -= arr[left]
        left += 1

    # 현재 합이 목표 값 m과 일치하는지 확인
    if current_sum == m:
        cnt += 1

print(cnt)