[알고리즘 일기 - 파이썬] 175. 부분합

문제 175. (2022-02-05)

 

1806번: 부분합

Baekjoon 1806. 부분합

[파이썬(python) 풀이]

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

 

---

입력

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

 

---

출력

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

 

---

입력 예시

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

 

---

출력 예시

2

 

---

❧ 정답

🔎IDEA) 리스트의 맨 앞에 원소부터 for문을 돌며 부분합 구간에 포함 시키고 제외하는 과정을 반복하며 구하고자 하는 최소 길이를 및 최적의 부분합을 찾는다.

• 투포인터 적용 : for 문의 i 값으로 부분합 구간의 start 인덱스를 움직이고, end로 부분합 구간의 end 인덱스를 움직인다.

 

• rst : 최소 길이의 값으로, 문제에서 찾는 값
• now : S 이상의 부분합 중 최댓값
• end : 현재 부분합 구간의 맨 끝 인덱스 값

[Line 8 - 13]
👉 Line 19 에서의 'Index Error'를 방지하기 위해 첫 번째 원소만 따로 빼서 처리를 해준다.
👉 부분합 구간으로 첫 번째 원소 arr[0]을 포함하며 S를 넘는 부분합의 길이(rst)와 부분합(now)을 설정한다.

 

[Line 15]
👉 부분합이 존재하지 않는 경우로, 리스트의 모든 요소를 더해도 S 미만인 경우를 처리해준다.

 

[Line 18]
👉 부분합 구간의 첫 시작 원소를 arr[1] 부터 해서 더이상 부분합을 구할 수 없을 때까지 최적의 부분합을 구하는 작업을 반복한다.

 

[Line 19 - 22]
👉 이전에 구한 최적의 부분합에서 이전 인덱스의 값을 빼고 우측 인덱스의 값을 더해준다.

• 부분합을 구하는 범위를 우측으로 한 칸 전체 이동했다고 보면 된다.

 

[Line 28 - 35]
👉 만약 새롭게 구하는 구간의 부분합이 S가 되지 않으면 탐색을 종료하고 다음 인덱스로 넘어간다.
👉 새롭게 구하고자 하는 부분합의 구간이 S를 넘으면 now을 기존 now값에서 맨 우측값을 뺀 값으로 갱신하고 rst값을 기존 rst값에서 1을 뺀 값으로 갱신한다.
👉 이후 이 과정을 다시 반복한다.

 

[Line 23]
👉 부분합 구간의 맨 끝 인덱스가 n(맨 끝까지 도달)에 도달했지만 부분합이 S를 넘지 못하는 경우로, 이후에는 더이상 값의 갱신이 이루어지지않으므로 전체 반복문을 종료한다.

 

[Line 25]
👉 부분합 구간의 맨 끝 인덱스가 n(맨 끝까지 도달)에 도달했지만 부분합이 S를 넘는 경우로, 해당 구간에서 맨 끝 원소를 하나씩 줄여가며 최적의 부분합을 찾는다.