BOJ 2515 전시장
알고리즘 문제풀이/BOJ
2019. 8. 9. 21:40
https://www.acmicpc.net/problem/2515 출처 : KOI (한국정보올림피아드) 중등부 2012 - 2번 대충 요지는, 이전 그림보다 $S$ 이상 높이가 큰 그림만 골라 나가면서 최대의 가격을 얻는 문제. 정렬해놓고 간단한 dp로 풀 수 있다. $\texttt{dp[i]}$ = $i$번째 그림까지 생각했을 때 얻을 수 있는 최대 가격 이라고 생각하면, 그림을 높이 순으로 정렬한 다음, $\texttt{dp[i]}$ 는 $i$번 그림 이전에 올 수 있는 가능성이 있는 $\texttt{dp[u]}$ 에 지금 보는 그림의 가격을 더한 값이거나 (이 경우, $i$번째 그림을 넣는 것이 올바른 답이라는 뜻) $i-1$번 까지 고려했을 때의 값 (이 경우, $i$번째 그림을 버리겠다는 뜻이다..
