[백준] Python 1806번 부분합

syeony·2024년 12월 12일
1

python

목록 보기
19/20

첫번째 풀이

# 시간초과 -> 찾아본 결과 <투포인터>라는 개념 찾았음

import sys
input = sys.stdin.readline

n,s = map(int,input().split())
arr = list(map(int,input().split()))
sum = 0
cnt = 0
cnt_arr = []

for i in range(len(arr)):
    for j in range(i,len(arr)):
        sum += arr[j]
        cnt += 1
        if sum >= s:
            cnt_arr.append(cnt)
            sum,cnt = 0, 0
            break

print(min(cnt_arr))

시간초과된 풀이
단순하게 이중for문으로 풀어본 것이다

두번째 풀이

# 투포인터 개념 이해 및 적용

import sys
input = sys.stdin.readline

n,s = map(int,input().split())
arr = list(map(int,input().split()))

left, right = 0, 0
sum = 0
min_num = sys.maxsize

while True:
    if sum>=s:
        min_num = min(min_num, right-left)
        sum -= arr[left]
        left += 1
    elif right == n:
        break
    else:
        sum += arr[right]
        right += 1

if min_num == sys.maxsize:
    print(0)
else:
    print(min_num)

투포인터라는 개념을 새롭게 알게되었다.
사실 이전에 비슷한 문제를 SWEA에서 풀었던 적이 있는데 그때 투포인터로 푼 사람도 있었는데 나는 그냥 이중for문으로 풀었는데 통과됐어서 또 이중for문으로 풀었던 것 같다.
백준은 확실히 시간초과가 엄격한 것 같다. 그래서 더 알고리즘을 찾아볼 수 있는? 좋은 것 같다.

profile
모바일 어플리케이션, cross platform과 iOS에 관심이 많은 개발자 오승연입니다

0개의 댓글