부분합

박고은·2025년 1월 27일
0

코딩테스트 연습

목록 보기
37/37

투 포인터 알고리즘

N, S = map(int, input().split())
arr = list(map(int, input().split()))

arr.append(0)
N = N+1

start, end = 0, 0
total = 0
answer = N+2

while end < N:
    if total >= S:
        answer = min(answer, end - start)
        total -= arr[start]
        start += 1
    else:
        total += arr[end]
        end += 1

print(answer if answer != N+2 else 0)

if-else문으로 구현하게 되면 배열의 마지막 숫자가 고려되지 X
-> end가 증가하고 while문에서 걸려서 answer 최소값 갱신 불가
-> 배열 마지막에 사용하지 않는 숫자 0을 추가하여 실행

N, S = map(int, input().split())
arr = list(map(int, input().split()))

start, total, answer = 0, 0, N+1

for end in range(N):
    total += arr[end]           # end 포인터 증가

    # total이 S에 가까워질 때까지 start 증가
    while total >= S:
        answer = min(answer, end - start + 1)
        total -= arr[start]     # start 포인터 감소
        start += 1

print(answer if answer != N+1 else 0)

-> for 루프로 end 포인터가 끝까지 증가
-> total이 S 이상 될 때까지 start 포인터 증가

0개의 댓글