[백준] 1806번 부분 합 파이썬 풀이

1806번: 부분합

[문제]

---

 

---

[코드]

import sys
#투포인트
input = sys.stdin.readline

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

start, end = 0, 0
result = 100001
total = 0

while True:
    if total >= s:
        result = min(result, end-start)
        total -= number[start]
        start+=1
    else:
        if end ==n:
            break
        total += number[end]
        end += 1

if result == 100001:
    print(0)
else:
    print(result)

---

[해설]

전형적인 투포인터 문제이지만...

고려할 상황이 조금 많은 문제이다

 

처음에는 투포인터의 위치를 어디에 둘까 고민을 했었다

처음과 끝에 두면 정렬이 되지 않아 있기 때문에 굳이 볼 필요가 없을 것이라는 생각을 했다

 

그래서 전통적인 투포인터 접근으로 처음에 시작과 끝을 설정하는 방식으로 접근했다

 

이번 문제의 핵심은 다음과 같다

1. 두포인터의 위치를 어디에 둘지

2. 만약 새로 추가한 값이 조건 값을 넘어갔을 때 시작점의 값을 뺐을 경우 조건 값을 넘어가는 경우를 처리하는 법

import sys
#투포인트
input = sys.stdin.readline

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

start, end = 0, 0
result = 100001
total = 0

먼저 총 수열의 길이와 목표값을 int로 받아서

n, s 변수로 저장해준다

 

그리고 수열을 리스트로 받아서 number로 저장해준다

 

그리고 투포인터의 핵심인 시작점과 끝점을 모두 0으로 지정해주고

우리가 원하는 값인 최소거리를 구하기 위해서 조건에서 최댓값인 100001을 임시 값으로 지정해준다

이는 알고리즘을 돌면서 최솟값으로 갱신될 것이다

 

그리고 시작점과 끝점 사이의 합을 total로 지정하여 초기값은 0으로 해준다

while True:
    if total >= s:
        result = min(result, end-start)
        total -= number[start]
        start+=1
    else:
        if end ==n:
            break
        total += number[end]
        end += 1

다음 while 문이 이번 문제의 핵심이다

쉽게 설명하자면 start - end 안에 있는 값들의 합이 우리의 목표한 값보다 큰 경우 - 조건만족

결과값과 현재 end - start = 거리를 입력해서 최솟값인 경우로 갱신해준다

 

그리고 그 합에서 start 값을 빼고 start에 +=1 를 해준다

만약에 start를 빼주었는데도 s보다 크다면 다시 if 문으로 들어와 위 루틴을 반복할 것이다

즉, start 와 end의 거리가 s보다 작아질 때 까지 반복할 것이다

---

그리고 만약 start - end 안에 있는 값들의 합이 우리가 목표한 값 s 보다 작은 경우 

그리고 end의 값이 마지막 위치와 같지 않다면

현재의 합에서 끝점을 추가해주고 

끝점에 1을 추가해준다

 

만약 같다면 더이상 볼 필요가 없기 때문에 while 문을 종료해준다  - 이미 필요한 경우의 수를 다 봤기 때문에