백준 1806번 부분합 : 마포 코딩박

문제

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

문제풀이

사용한 알고리즘 : 투 포인터

(1) (코드: 7)

 포인터 두개 lo, hi 에 대해 ' lo이상 hi미만 '의 값들의 합을 sum 이라고 설정하였습니다.

(2) (코드: 17~24) 

 투포인터를 진행하는 while 문을 돌립니다.
 1. sum >= S 인 경우 ans를 최신화 하고 sum에서 lo의 값을 뺀 후 lo++

 2. hi==N 인 경우 끝.

 3. sum<S 인 경우 sum에 hi값을 추가 한 후 hi++