[백준] 1806 부분합 (Python 파이썬)

www.acmicpc.net/problem/1806

1806번: 부분합

문제 설명

수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는것 중, 가장 짧은 것의 길이를 구하는 문제이다.

---

풀이 과정

전형적인 투포인터 문제이다.

시작점과 끝점을 적절히 이동시키며 그 사이에 있는 부분들의 합을 이용해 정답을 찾는 문제이다.

 

처음에 시작점과 끝점을 0으로 둔다.

그 후 시작점과 끝점을 움직이면서 구간의 길이를 조절하게 되는데,

현재 구간이 S보다 작다면, 구간을 더 늘려야 하므로 끝점을 뒤로 움직여 구간을 늘려주고

현재 구간이 S보다 크다면, 구간을 더 줄여야 하므로 시작점을 뒤로 움직여 구간을 줄여준다.

 

처음 풀었을 때는 mysum이라는 변수 대신에,

매번 sum[start:end+1] 을 통해 합을 구해주었더니 시간초과 오류가 났다.

 

그래서 mysum 변수를 통해 값을 저장해두어, 그 값에 더 더하거나 빼는 방식으로 변경하였고 통과하였다.

import sys
n, s = map(int, sys.stdin.readline().split())
nlist = list(map(int, sys.stdin.readline().split()))

start, end = 0, 0
flag = 0
shortest = n
count = 0
mysum = nlist[0]

while end < n:

    if mysum < s:   # 현재 구간합이 s보다 작으면
        end += 1    # 현재 구간의 끝점을 늘려준다
        if end < n: # 끝이 n을 벗어나면 안되기 때문에 범위 고려
            mysum += nlist[end]

    else:           # 현재 구간합이 s보다 크거나 같을 경우
        flag = 1    # 답을 찾을 수 있다는 표시
        if shortest > end-start:    # 현재까지의 최소거리보다 짧으면
            shortest = end-start+1  # 최소거리 갱신

        if start < end:             # 구간 시작점이 끝점보다 앞에있으면
            mysum -= nlist[start]   # 구간 시작점을 하나 늘린다
            start += 1
        else:                       # 구간 시작점이 끝점과 같거나 뒤에있으면
            end += 1                # 구간 끝점을 하나 뒤로 늘려서 end가 start뒤에 오도록 유지
            if end < n:
                mysum += nlist[end] # 끝점을 늘려가며 부분합 추가

if flag==1:
    print(shortest)
else:
    print(0)

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !