[백준 1806] 부분합

[ 백준 1806 : 부분합 ]

간만에 손도 풀고 감도 익힐겸 사이트에 들어갔는데 그냥 먼저 보이는 문제 하나 집어서 풀었다.
이 문제를 처음 읽고 메모이제이션해놓으면 편할것 같은데.. 생각하고 일단 바로 메모를 해놨다.
DP라는 배열에 현재까지 배열의 합을 저장해 놓고 0번 인덱스 부터 N번째 인덱스까지 이분탐색으로 S를 넘는 값이 있는지를 탐색했다.

그리고 조금이나마 시간을 아껴보려고 배열을 입력받을때 S를 넘는 값이 있으면 바로 1을 출력한 뒤 프로그램을 종료시켰다.
그렇지 않다면
로직은 위에서 말한대로

0번 인덱스부터 N번째 인덱스를 탐색한다.
만약 5번 인덱스를 탐색할때
이분탐색으로 0번부터 5번을 L과 R로 정한 후 MID=(L+R)/2값을 살펴본다.
DP[5] - DP[MID] 이런식으로 하면 MID부터 현재 인덱스까지의 합이 몇인지 쉽게나온다.

간단한 이분탐색 응용문제라고 생각한다.