[백준/python] 2003: 수들의 합 2

문제

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

2003번: 수들의 합 2

 

설명

- 투포인터 및 누적합

- for 문을  처음부터 끝까지 이용한다면 데이터 범위가 많고, 시간 제한이 짧을 경우에는 시간 초과가 발생할 경우가 많다. 그래서 처음부터 전수조사(완전탐색) 하는 것이 아니라, 포인터를 이용하여 원하는 인덱스 값들을 조절하여 필요한 값들을 찾도록 하는 것이다.

- left, right = 0, 1 로 두는 경우에는 범위를 점점 넓히는 경우도 있고, 코알라 스터디에 있듯이 양 쪽 끝에서 범위를 좁혀가는 경우도 있다.

- 투포인터에 대해서 이론은 이해됐지만 구현에 있어서는 조금 와 닿지는 않았는데 다음 블로그를 참고하면서 이해를 했다. 추가로, 투포인터와 유사한 슬라이딩 윈도우 개념도 알아볼 수 있었다.

https://m.blog.naver.com/kks227/220795165570

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)

 

코드

n, m = map(int ,input().split())
li = list(map(int, input().split()))

left, right = 0, 1
ans = 0

while (left <= right and right <= n):

    sum_nums = li[left:right]
    cnt = sum(sum_nums)

    if cnt > m:
        left += 1
    elif cnt == m:
        right += 1
        ans += 1
    else:
        right += 1

print(ans)