BOJ - 수들의 합2(2003)

실버2 : two pointer 문제이다.

풀이

• 투포인터는 i이상 j미만으로 짠다.
• 같을 경우는 i를 늘려서 파악한다. 즉 왼쪽이 더 많이 따라오는 구조
• 일단 왼쪽이 갈 수 있으면 최대한 배려해주는 느낌
• 근데 못가, 그러면 이제 오른쪽이 기준이 되어서 판단
• 어차피 i, j가 같아진다면 sum 이 0이 되어서 j를 늘릴 수 밖에 없다.
• 끝까지 j가 갔는데, 값이 M보다 크면 i를 늘려가면서 후보값이 있는지 확인해볼 수 있다.
• 하지만 끝까지 갔는데 i이상 j미만의 값이 M보다 작다면 더이상 가능성이 없으니 종료한다.

i이상 j미만이 중요하다. 그리고 마지막처리가 중요한데, 이러한 부분에 있어서 다양한 결과를 예상하고 손코딩하는 것이 중요하다는 것을 느꼈다.

지금 같은 경우 파악해볼 만한 것이, 결국 마지막에 도착했을 때, 값이 큰 경우, 같은 경우, 작은 경우에 대해 판단해보면 된다.

Code

import sys
 
input = sys.stdin.readline
 
n, m = map(int, input().split())
a = list(map(int, input().split()))
i, j, ans, bound = 0, 0, 0, 0
 
while True:  # i이상 j미만의 bound를 확인할 것임
    if bound == m:  # 먼저 지금 값이 정답인지 확인
        ans += 1
 
    if bound >= m:
        bound -= a[i]
        i += 1
    elif j == n:  # 특정 i부터 j미만값까지 봤는데, j가 N이야. 즉 끝까지 간거지
        break  # 근데 값이 이미 M보다 작아, 그럼 할 수 있는 건 i를 늘리는 것 밖에. 근데 그건 무조건 작지
    else:
        bound += a[j]
        j += 1
 
print(ans)

Reference

• 백준(2003번) - 수들의 합2