[baekjoon] 백준 1806번(파이썬): 부분합

문제

1806번: 부분합

알고리즘

- 투 포인터를 통해 문제를 수행한다.

- 시작 위치와 마지막 위치를 저장하고 그 위치 사이에 수열의 합을 s와 비교하며 반복문을 수행한다.

- 수열의 합이 s보다 크거나 같다면 그때의 길이를 최소 길이와 비교하고 현재 수열의 시작 위치 값을 빼주고 현재 수열의 시작 위치를 한 계단 앞으로 이동시킨다.

- 수열의 합이 s보다 크거나 같지 않다면 수열을 만들 수 있는지 확인해준다.

- 이때, 맨 끝 위치가 n과 같다면 더 이상 수열의 합으로 s이상의 값을 만들 수 없다.

- 그게 아니라면 현재  수열의 마지막 위치 값을 더해주고 수열의 마지막 위치를 한 계단 앞으로 이동시킨다.

- 반복문이 끝난 후 수열의 최소 길이가 반복문 이전과 바뀌었는지에 따라 수열의 최소 길이를 출력해주면 된다.

코드

import sys


n, s = map(int, sys.stdin.readline().split())
num = list(map(int, sys.stdin.readline().split()))
target = 0
left = 0
right = 0
answer = 1e9

# 반복문을 통해 수열을 확인
while True:

    # left부터 right까지 수열의 합이 s를 넘는다면
    if target >= s:

        answer = min(answer, right - left) # 매 순간 최소 길이로 초기화
        target -= num[left] # 현재 수열의 시작 위치 값을 빼주고
        left += 1 # 현재 수열의 시작 위치를 한 계단 앞으로 이동

    # left부터 right까지 수열의 합이 s를 넘지 않는다면
    else:

        # 맨 끝 위치가 n과 같다면 반복을 멈춰준다. s를 넘는 수열을 만들 수 없기 때문 
        if right == n:
            break
        
        target += num[right] # 현재 수열의 마지막 위치 값을 더해주고
        right += 1 # 수열의 마지막 위치를 한 계단 앞으로 이동

# answer가 바뀌지 않았다면 0 출력 바뀌였다면 바뀐 값 출력
print(0) if answer == 1e9 else print(answer)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법