1806(부분합) - 파이썬

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

1806번: 부분합

---

내 풀이

시도1

import sys
input = sys.stdin.readline
def solution():
    n,s = map(int,input().split())
    candi = list(map(int,input().split()))
    
    answer=[]

    for i in range(len(candi)):
        m_sum=0
        count =1
        m_sum += candi[i]
        for j in range(i+1,len(candi)):
            if m_sum == s:
                answer.append(count)
                break
            elif m_sum > s:
                break
            m_sum += candi[j]
            count +=1
    return min(answer)
    



print((solution()))

사실 아무생각없이 이중루프를 돌렸는데 이제와서 생각해보니까 안되는게 당연하다. 항상 문제조건을 보고 문제를풀자

 

두번째시도

 

def solution():
    n,s =  map(int,input().split())

    lists = list(map(int,input().split()))
    sum_parts= 0
    starts=0
    ends=0
    answer=int(1e9)
    while True:
        if sum_parts >= s:
            answer = min(answer,ends-starts)
            
            sum_parts -=lists[starts]
            starts +=1
        else:
            if n==ends:
                break
            sum_parts +=lists[ends]
            ends +=1

    print(0 if answer==1e9 else answer)
    
    
solution()

 

두번째는 시간초과를 막기위하여 이중루프를 없앴다. 풀다보니 예전에 부분합 풀었던 기억이 있어서 더듬더듬 풀었다..

찾아보니 투 포인터라는 알고리즘이라고 한다.

---

 

---

다른사람의 풀이

 

---

---