[알고리즘/투 포인터] 1806번 : 부분 합 - python

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

1806번: 부분합

---

• 문제
• 소요시간 : 1시간 실패

---

• 설계하기(접근방법) 

1. 입력받기

배열을 입력받는다

 

2. 구현하기

처음에는 길이가 1인 부분합,

2인 부분합....

식으로 구했으나 결국에는 시간초과가 났다

 

아이디어를 바꾸어

 

s 이상일 때까지 p2를 움직이고

s 이상이 되면 최소 길이와 비교하고

 

s 미만이 될때까지 p1을 증가시키는 방식을 떠올렸다

 

아이디어는 맞았으나

구현을 하기 못해 실패했다

 

3. 출력하기

최소 길이를 출력한다

 

---

• 코드(출력)

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

small = 10e9

p1, p2 = 0,0
total = 0

while True:
    if total >= s :
        small = min(p2 - p1, small)
        total -= n_list[p1]
        p1 += 1
    elif p2 == n:
        break
    else:
        total += n_list[p2]
        p2 += 1

if small == 10e9:
    print(0)
else:
    print(small)

---

• 얻어갈 부분

1. while문 내에 while문을 돌릴 수도 있지만 if 절로 조건을 처리해서 굳이 또 while문을 쓰지 않아도 된다

2. 최소값을 구하는 경우 

a = min(a, now) 형태로 구하자