투 포인터. [1806]

[1. 문제 설명]

10,000 이하의 자연수로 이루어진 길이 N 인 수열에서

연속된 부분 합 중 그 합이 S 이상이 되는 것 중 가장 짧은 것의 길이를 구한다.

---

[2. 풀이 접근]

먼저 부분 합을 구한다.

연속된 부분 합을 찾기 위한 탐색을 해야 하는데,

 

자연수로 이루어진 수열의 부분 합은 값이 증가할 수 밖에 없으므로,

여기서는 head 와 tail 을 맨 앞에서 부터 움직이도록 한다.

 

최초 head 를 고정 시킨 상태에서 tail 을 움직이면서 부분 합이 S 이상이 되는지 확인하도록 한다.

S 이상이 된 경우 head 를 움직이도록 한다.

 

head 를 움직인 경우 S 미만이 되면, tail 을 움직이도록 한다.

부분 합은 오름차순으로 되어있기 때문이다.

 

=== 실수했던 사항 ===

불가능 한 경우 0을 출력해야 하는데, MaxInt 를 그대로 출력했던 것이 있었다.

문제를 잘 읽도록 한다.

---

[3. 코드]