[BOJ] 1806 부분합

date

Aug 5, 2023

slug

boj-1806

author

status

Public

문제 링크

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

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

문제풀이

우선 Prefix_sum을 구해주고

Two_pointer의 시작을 처음으로 둔후,

end가 끝까지 갈때까지 구해준다.

arr[end] - arr[start-1]은

end와 start의 구간합을 나타내는것이므로 이 것이 S를 넘을떄

min_length를 갱신해준다.

이때 start=end가 같을 경우가 존재하는데 이때는

원소 한 개가 S를 넘는경우일때 min_length = 1로 최솟값 갱신해준다.

파이썬 문제풀이 코드


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

arr = [0] + list(map(int, input().split()))

for i in range(1, N+1):
    arr[i] += arr[i-1]  # prefix sum
    

start = end = 1
min_length = 1e8
# print(arr)
while start <= end:
    # print(start, end)
    # print(min_length)
    if end >= N+1: # end가 배열을 넘어가면 안됨
        break
    if start == end:
        if arr[start] - arr[start-1] >= S:
            min_length = 1
            break
        else:
            end += 1
        continue
    if arr[end] - arr[start-1] >= S: # 구간 누적합이 S보다크면
        min_length = min(end-start+1, min_length) # 구간 누적합 길이 갱신
        # print(min_length)
        start += 1 # 길이를 작게하고 한번더 갱신해봄
    else:
        end += 1 # end 길이를 해봄
    
if min_length >= 1e8:
    print(0)
else:
    print(min_length)

시간복잡도

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력


10 15
5 1 3 5 10 7 4 9 2 8

예제 출력

알고리즘 분류

누적 합

두 포인터