백준 1806번 부분합 문제풀이, 파이썬

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

---

<문제>

 

1806번 문제의 내용은 아래와 같습니다. 

 

 

부분합 

문제

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

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력 1 복사

10 15
5 1 3 5 10 7 4 9 2 8

예제 출력 1 복사

2

---

 

 

<작성한 코드>

 

#부분합
import sys

N, S = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))

start, end = 0, 0
sum = 0
length = 100001

while True:
  if sum >= S:
    length = min(length, end-start)
    sum -= nums[start]
    start += 1
  elif end == N:
    break
  else:
    sum += nums[end]
    end += 1

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

---

 

 

<코드 풀이>

 

본 문제는 이름부터가 부분합이라 prefix_sum, 구간합 알고리즘을 사용해서

이전과 같이 동일하게 풀려고 접근을 시작했는데 뭔가 이상함을 감지했다. 

문제에서 주어진 구간의 합을 구해서 그 결과값을 출력하는 것이 아니라 

연속된 수들의 부분합들 중 주어진 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 것이 본 문제의 요구사항이다. 

==> 따라서 본 문제는 투 포인터 알고리즘을 사용해서 풀었다. 

 

 

import sys

N, S = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))

역시나 가장 먼저, 문제에서 요구하는 입력값들을 받아주기 위한

초기 세팅을 먼저 해주었다. 

 

 

start, end = 0, 0
sum = 0
length = 100001

다음으로는 투 포인터 알고리즘을 위한 세팅을 위와 같이 해주었다. 

여기서 length 에는 조건을 만족하는 부분합의 구간 길이들을 넣을 것인데,

초기값을 100,001로 설정한 이유는 문제에서 조건으로 걸린 수열의 최대 길이가 100,000이기 때문이다. 

 

 

 

while True:
  if sum >= S:
    length = min(length, end-start)
    sum -= nums[start]
    start += 1
  elif end == N:
    break
  else:
    sum += nums[end]
    end += 1

다음으로는 위와 같은 반복문을 돌면서 length라는 변수에 

조건을 만족하는 부분합의 길이 중 최소가 되는 것을 재할당해준다. 

만약 특정 구간의 부분합이 조건의 S보다 작다면 end의 값을 1 늘려주어 구간을 오른쪽으로 한칸씩 옮기고

특정 구간의 부분합이 조건의 S보다 크다면, start의 값을 1씩 늘려준다. 

 

 

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

만약 위의 반복문을 돌면서 S보다 큰 조건을 만족하는 부분합이 존재하지 않는다면

length라는 변수에는 아무런 값도 재할당 되지 않아서 그대로 100001이라는 초기값을 가질 것이다. 

그런 경우에는 '0'을 출력해주고, 아니라면 length를 출력해주면 된다.