[백준 2003] 수들의 합2 (with Python / 투포인터)

문제링크

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

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

출력

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

예제 입력 1 복사

4 2
1 1 1 1

예제 출력 1 복사

3

예제 입력 2 복사

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

예제 출력 2 복사

3

 

문제풀이

보자마자 투포인터로 풀면 되겠다고 생각했다.

하지만 오랜만에 접한 탓인지,

순간 i, j의 값이 같을때와 다를때를 구분해서 풀려고했다.

 

하지만 이문제는 i~j까지의 합을 알면 되는 문제이므로 같을때를 따로 분리해서 로직을 실행할 필요가 없다.

 

핵심

포인터 변수 2개로 리스트 전체를 탐색하며 구간합과 M값을 비교

 

1.  구간합 구하기 => ★인덱스 슬라이싱, sum() 활용

    구간을 for in range()로 정하여 돌렸더니 보기좋게 시간초과가 났다.

    내부적으로 최적화된 메서드들 잘 활용하자...

2. 구간합 < M  :  j값 1 증가 (우측 포인터 이동 / 구간합 늘리기 위해)

    구간합 > M  :  i값 1 증가 (좌측 포인터 이동 / 구간합 감소 위해)

    구간합 == M :  cnt 증가 및 j값 1증가 (우측 포인터 이동)

 

cf. 투포인터 알고리즘 시간복잡도는 최악의 경우에도 O(N)이다.

두개의 포인터가 항상 l <=r 로 움직이기 때문에 두 포인터가 증가하는 과정은 최대 N번만 반복될 것이다.

 

코드

N, M = map(int,input().split())
A = list(map(int, input().split()))
i = 0
j = 0
cnt = 0

while i < N and j < N:
    # A[i]와 A[j]합을 구해 M보다 작으면 j값 증가, 크면 i값증가, 같으면 cnt += 1
    testSum = sum(A[i:j+1])

    if testSum < M:
        j += 1
    elif testSum > M:
        i += 1
    else:
        cnt += 1 
        j += 1

print(cnt)