[BOJ][🟡4][백준#01806] 부분합

문제 출처

BAEKJOON Online Judge #1806

문제

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

입력

첫째 줄에 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

출력

2

My Sol

import sys
input = sys.stdin.readline

N, S = map(int, input().split())
arr = list(map(int, input().split()))
sum_lst = [0]*(N+1)

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

ans = 100001
s = 0
e = 1

while s!=N:
    if sum_lst[e] - sum_lst[s] >= S:
        if e-s < ans:
            ans = e-s
        s += 1

    else:
        if e != N:
            e += 1
        else:
            s += 1

print(ans) if ans < 100001 else print(0)

투포인터 알고리즘을 사용하는 문제였다. 어떻게 푸는지 몰라서 풀이(출처)를 참고했다.

숫자 리스트를 입력으로 받으면 누적합 리스트를 만들고, 0과 1부터 시작하는 포인터를 만들어 S 경계를 기준으로 포인터를 하나씩 이동시키면서 누적합 차이가 S 이상이라면 e와 s 값 차이를 최솟값 ans에 계속 갱신하며 인덱스가 N 일 깨까지 달려간다. S보다 누적합 차이가 작으면 e를 늘려주어 S에 근접하도록 한다.

결과

맞았습니다!!

모범답안

출처

answer = 100000

n, m = map(int,input().split())
nums = list(map(int,input().split()))

i = 0
j = 0
s = nums[0]

l = 0
while i < n:
    
    if s >= m :
        l = j - i + 1
        if answer > l:
            answer = l
        
        s -= nums[i]
        i += 1
        
    else:
        j += 1
        if j == n:
            break
        s += nums[j]
    
print(0 if answer == 100000 else answer)

연산시간이 20% 정도 빠른 풀이를 발견해 분석해보려 한다. 나는 누적합을 계산해주고 시작했는데, 이 분은 인덱스를 이용해 숫자 리스트에서 값을 더해주고 빼주는 과정을 통해 처음에 누적합 리스트를 만드는 과정을 생략할 수 있었다.