220315 - 부분합

◾ 부분합 : 백준 1806번

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

문제

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

---

입력

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

출력

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

입출력 예

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

---

◾ 풀이

1. 해설

• 투 포인터를 이용해 O(n)의 시간 복잡도로 해결할 수 있다.
• 부분합의 시작, 끝 인덱스를 이용해 값을 탐색한다.
  • 현재 값이 더 작다면 (끝 인덱스 + 1)을 통해 값을 더해준다.
  • 현재 값이 크거나 같다면 (시작 인덱스 + 1)을 통해 값을 빼준다.
  • 부분합의 길이 : 끝 인덱스 - 시작 인덱스 + 1
  • 끝 인덱스가 범위를 넘어서거나 시작 인덱스가 끝 인덱스보다 커질 경우 종료한다.

---

2. 프로그램

1. n, s, sequence 입력
2. left(시작 인덱스), right(끝 인덱스) 초기화
3. 부분합과 s를 비교하며 탐색
   • 부분합이 작다면
     • right + 1(단, right < n)
     • 부분합 + sequence[right]
   • 부분합이 크거나 같다면
     • 부분합의 길이가 작은 경우 선택 : right - left + 1
     • 부분합 - sequence[left]
     • left + 1(단, left <= right)

# 코드
n, s = map(int, input().split(' '))
sequence = list(map(int, input().split(' ')))

left = 0    # 시작 인덱스
right = 0   # 끝 인덱스
size = 1000000
sub_sum = sequence[0]

while True:
    # 부분합이 작을 경우
    if sub_sum < s:
        right += 1  # 끝 인덱스 + 1
        # 범위를 벗어날 경우 종료
        if right >= n:
            break
        # 끝 인덱스의 값 추가
        sub_sum += sequence[right]
    else:
        # 길이가 더 작은 경우 선택
        size = min(size, right - left + 1)
        # 시작 인덱스의 값 빼기
        sub_sum -= sequence[left]
        # 시작 인덱스 + 1
        left += 1
        # 시작 인덱스가 끝 인덱스보다 커질 경우 종료
        if left > right:
            break
        
# size의 값이 초기값일 경우 0 반환
if size == 1000000:
    print(0)
else:
    print(size)

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