[알고리즘] BOJ 1806번 - 부분합(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

7 / 50

 

탐색

8 / 50

 

기초 동적 프로그래밍

6 / 50

---

투포인터

2 / 10(NEW!)

 

이분탐색

0 / 10

---

문제

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

1806번: 부분합

→ solved.ac 기준 골드 5

---

문제 해결 아이디어

수열에서 부분합 ⇒ 투 포인터 문제임을 직감

→ 나동빈님 알고리즘 유튜브 강의 중 투 포인터 예제(특정한 합을 가지는 부분 연속 수열 찾기) 문제와 비슷

→ start, end pointer가 처음부터 시작하는 투 포인터를 사용해서 부분합을 찾고, 그 중 가장 작은 값만 기록

---

구현

내 풀이

import sys
input = sys.stdin.readline

INF = 1e9
n, s = map(int, input().split())
array = list(map(int, input().split()))

start = 0
end = 0
interval_sum = 0
answer = INF

for start in range(n):
  while interval_sum < s and end < n:
    interval_sum += array[end]
    end += 1
  
  if interval_sum >= s:
    answer = min(answer, end - start)
  interval_sum -= array[start]
  
if answer == INF:
  print(0)
else:
  print(answer)

---

메모

• 걸린 시간: 30분
  • 사실 투포인터 그대로 가져다쓰고 하면 되는 거였는데 위 알고리즘에서 end 인덱스를 잘못 생각하고 헛다리를 짚다가... 시간을 더 소요해버렸음..

---