[ 백준 1806 : 부분합 ]
간만에 손도 풀고 감도 익힐겸 사이트에 들어갔는데 그냥 먼저 보이는 문제 하나 집어서 풀었다.
이 문제를 처음 읽고 메모이제이션해놓으면 편할것 같은데.. 생각하고 일단 바로 메모를 해놨다.
DP라는 배열에 현재까지 배열의 합을 저장해 놓고 0번 인덱스 부터 N번째 인덱스까지 이분탐색으로 S를 넘는 값이 있는지를 탐색했다.
그리고 조금이나마 시간을 아껴보려고 배열을 입력받을때 S를 넘는 값이 있으면 바로 1을 출력한 뒤 프로그램을 종료시켰다.
그렇지 않다면
로직은 위에서 말한대로
0번 인덱스부터 N번째 인덱스를 탐색한다.
만약 5번 인덱스를 탐색할때
이분탐색으로 0번부터 5번을 L과 R로 정한 후 MID=(L+R)/2값을 살펴본다.
DP[5] - DP[MID] 이런식으로 하면 MID부터 현재 인덱스까지의 합이 몇인지 쉽게나온다.
간단한 이분탐색 응용문제라고 생각한다.
-
[ 백준 2528 : 사다리 ] 시뮬레이션문제 시뮬레이션이나 구현 문제의 차이점을 잘 모르겠다. 나는 시간이나 상황에따라 계속 변하는 것을 구현 하는것은 시뮬레이션이라 하고 딱 멈춰진 시간, 상황에 맞는 답을 구하는 것은 구현이라고 생각하... -
[ 백준 1389 : 케빈 베이컨의 6단계 법칙 ] 한 지점을 기준으로 목표점에 얼마나 많은 간선을 지날 수 있는지를 묻는다. 그리고 그 수의 합이 가장 작은 기준 지점이 어떤 점인지를 묻는 문제이다. N이 100이다. 1을 기준으로 하고 ...
-
[ 백준 1806 : 부분합 ] 간만에 손도 풀고 감도 익힐겸 사이트에 들어갔는데 그냥 먼저 보이는 문제 하나 집어서 풀었다. 이 문제를 처음 읽고 메모이제이션해놓으면 편할것 같은데.. 생각하고 일단 바로 메모를 해놨다. DP라는 배열에 현재까...
댓글 없음:
댓글 쓰기