[백준 1806] 부분합

[BanApp]

pypy3

import sys

n, m = map(int, sys.stdin.readline().split())

arr = list(map(int, sys.stdin.readline().split()))

ans = 1000001

s = 0
e = 0
c = 0

while 1:
    if c >= m:
        ans = min(ans,e-s)
        c = c - arr[s]
        s = s + 1

    elif e == n:
        break

    else:
        c = c + arr[e]
        e = e+1

if ans == 1000001:
    ans = 0

print(ans)

처음에 방향을 잘못 잡아서 굉장히 해맸다..
처음에는 양쪽 끝에서 포인터를 출발 시켜서 양끝을 비교하면서 작은 애들을 먼저 제거하면 풀릴거라고 생각했다.
이렇게 풀면 대부분 맞지만 가장 큰 값이 중간쯤 위치에 있는 경우에 미묘하게 1,2개 차이로 오답이 나온다. 잘못된 풀이라는 것이다.
계속 삽질을 하다가 투포인터 문제는 양끝에서 출발해서 만나거나 같이 출발하는 경우가 대부분이라는 생각에 s와 e를 같이 출발하는 위치에 뒀다.
이게 최대한 짧은 것을 찾는 문제라서 s의 위치가 증가할수록 값이 감소하고 e가 증가할수록 ans값이 증가한다는 것을 알고 포인터 위치가 0에서 출발해야 한다는 사실만 알면 쉽게 구할 수 있었다.
리스트 슬라이싱해서 sum 함수 사용하면 시간초과가 나기 때문에 c라는 변수에 값을 저장해 놓고 한번씩 더하고 빼주면 훨씬 효율적으로 만들 수 있다.
반복문 한번 실행될동안 증가,감소 둘중 하나만 이루어지기 때문이다.
그렇게 해서 c값이 m보다 크거나 작을경우 길이가 기존 ans보다 작으면 ans로 대체된다.
반복문에서 ans값이 한번도 안바뀐 경우 주어진 원소들로 m을 만들 수 없는 상황이라서 0을 출력해주고 그렇지 않은 경우 ans값을 출력해주면 정답!