1806. [Python]부분합

1. 문제

 

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

 

2. 접근 방법

 

• 시간 제한: 0.5초
• 메모리 제한: 128MB
• 투 포인터
• 누적합

 

3. 파이썬 코드

 

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

left = 0
right = 0
# 누적합 구하는 변수
total = 0
# 최소 길이 측정
minLength = 10**9
# right 값이 끝에 도달할때까지
while right < N:
    # right 인덱스를 계속해서 더해나감
    total += numList[right]
    # 합이 S보다 크거나 같아지는 경우
    if total >= S:
        # S값보다 작아질때까지 left 값 더해나감
        while total >= S:
            # right - left 길이 체크
            check = right - left
            # 최소 길이가 더 큰경우 갱신
            if minLength > check:
                minLength = check
            # 합에서 left 뺴고 left 1 증가
            total -= numList[left]
            left += 1
    right += 1

# 최소 길이가 초기값인 경우 0 출력 외에는 minLength에서 +1 해줌
if minLength == 10**9:
    print(0)
else:
    print(minLength+1)

 

4. 문제를 풀고난 후 생각

 

• 투 포인터 문제를 많이 접해보면 비슷한 유형의 문제들이 많은 것 같다.
• 앞선 다른 투 포인터 문제의 유형과 비슷한 양상을 띄고 있어서 푸는데 그렇게 오래 걸리진 않았다.
• left, right 인덱스를 통해서 right 값을 N 까지 증가시키며 더해나가며 원하는 목표값인 S와 비교해가며 작아질 때까지 left 인덱스를 증가시키며 포인터를 이동시켜준다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 투 포인터
• 누적합