백준 1806번 - 부분합

출처 : 1806번: 부분합 (acmicpc.net)

1806번: 부분합

 

---

 

부분합 성공출처다국어분류

한국어   

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

0.5 초 (하단 참고)

128 MB

27112

6976

4965

25.595%

문제

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

입력

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

출력

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

 

---

 

[ 문제 설명 ]

 

 

2003번 문제와 매유 유사하고, 조금만 바꾸면 풀 수 있는 문제입니다.

 

2003번 참고용 : 백준 2003번 - 수들의 합 2 (tistory.com)

백준 2003번 - 수들의 합 2

 

코드를 보면서 이해하시는게 더빠를 듯 합니다.

다만 2003번과 조금 차별되는 부분은 아래와 같습니다.

( 중요시되는 코딩 부분 )

    if sum >= m:
        min_len = min(min_len, right - left)  # 바뀐 부분
        sum -= numbers[left]
        left += 1

이 부분에서 min_len 값을 sum의 조건을 넘을 때마다 확인하는 방법으로 최신화해서 끝까지 남은 min_len을 출력하는 방법입니다.

 

---

 

[ 코드 ]

 

import sys

n, m = map(int, input().split())
numbers = list(map(int, input().split()))

left = 0
right = 0
sum = 0
min_len = sys.maxsize
# unions = []
# unions_len = []

# 순서가 있어야 하는 이유가 있다. while 문이 종료되는 시점을 고려하면 이해 가능
while True:
    # print(unions)
    if sum >= m:
        min_len = min(min_len, right - left)  # 바뀐 부분
        sum -= numbers[left]
        left += 1

    # print(right, left)
    elif n == right:
        break

    else:
        sum += numbers[right]
        right += 1


# print(res)
if min_len == sys.maxsize:
    print(0)
else:
    print(min_len)

---

후기

 

음... 같은 원리지만 다른 방법으로도

풀었는데 그 코드는 틀린다고 나오는데

이번에 복습하면서도 알아내지 못했네요..