[백준 BOJ / Python] 1806번 부분합 Prefix Sum (누적합)

문제

10000 이하의 자연수로 이루어진 n 길이의 수열에서 부분합이 s 이상이 되는 것 중 최소 길이를 구하는 문제이다.

풀이

• 이 문제는 1차원 배열의 부분합을 구하여 크기를 비교하고 최소 길이를 구하면 된다.
• 누적합을 구하면서 해당 위치 이전까지의 부분합 중 s 이상인 경우, 최소 길이를 업데이트한다.
• 예를 들어 4번째 칸까지 누적합을 구했을 때, s 가 7이라면 최소 길이는 3이 된다.

알고리즘

1. 누적합을 담을 dp list를 n+1 길이로 생성한다.
2. 최소 길이를 담을 ans 변수를 생성한다.
3. for 문을 n 번 돌면서 누적합을 계산한다.
   1. 최소 길이에 맞춰 부분합을 계산하고 만약 부분합이 s 보다 작다면 이후에도 더 작을 것임으로 중단해준다.
   2. 만약 s보다 크다면 최소 길이를 줄일 수 있다는 의미임으로 ans를 업데이트 해준다.
4. 만약 ans가 최초 가정했던 큰 수에서 변하지 않았다면 s보다 큰 부분합이 불가능했다는 의미임으로 0을 출력한다.
5. ans가 변했다면 최소 길이를 출력한다.

Python 코드

n,s = map(int,input().split())
a = list(map(int,input().split()))
def sol():
    dp = [0]*(n+1)
    ans = 100001
    for j in range(1,n+1):
        dp[j] = dp[j-1] + a[j-1]
        for i in range(max(0,j-ans),j):
            if dp[j]-dp[i] < s:
                break
            ans = min(ans,j-i)
    if ans == 100001:
        print(0)
    else:
        print(ans)
sol()

다른 풀이

• 두 포인터 방법을 통해 부분합을 구하는 방법도 사용할 수 있다.
• 시작과 끝을 0으로 초기화 한 뒤에 부분합이 s보다 작으면 끝을 한 칸 뒤로 옮기고, s보다 크면 시작을 한 칸 뒤로 이동시키면서 최소 길이를 탐색하는 것이다.
• 두 포인터 방법이 위의 누적합 방법보다 더 빠르게 답을 찾았다.

Python 코드

n,s = map(int,input().split())
a = list(map(int,input().split()))
def sol():
    # 부분합, 부분수열의 시작점, 끝점
    sub, start, end = 0, 0, 0
    ans = 100001
    # 한칸씩 이동하면서 부분합을 비교
    while True:
        # 만약 부분합이 s보다 크면 부분합의 길이를 업데이트
        if sub >= s:
            ans = min(ans, end - start)
            # 시작점을 오른쪽으로 한칸 이동하면서 이전에 더해준 값은 빼주기
            sub -= a[start]
            start += 1
        else:
            # 마지막을 넘었다면 멈추기
            if end == n:
                break
            # 부분합이 s보다 작으면 끝점을 오른쪽으로 한칸이동
            sub += a[end]
            end += 1            
    if ans == 100001:
        print(0)
    else:
        print(ans)
sol()

문제 출처

1806번: 부분합