다이나믹 프로그래밍은 사실 다이나믹과는 아무 상관이 없다. 문제를 작게 나누어 답을 저장해가며 큰 문제를 해결하는 문제 해결 방법으로 메모이제이션 프로그래밍으로도 불린다.
백준에서 어떻게 풀어야할지 막막한 문제들은 대개 DP 문제들이 많더라..
https://www.acmicpc.net/problem/11052
11052 번: 붕어빵 판매하기 www.acmicpc.net
1 개에 1 원인 붕어빵을 왜 2 개에 5 원에 판매하는지는 모르겠지만(…), 이 문제는 DP 를 사용해야하는 문제이다.
단순히 생각해서 매번 가장 이익이 큰 경우만을 선택하게 하면, 1(4) 10(20) 16(32) 17(17) 같은, 비율로는 3 개를 파는것이 더 크지만 그 다음 1 을 팔아야하는 경우를 고려할 수 없게 된다. 따라서 모든 경우를 다 고려할 수 있는 다이나믹 프로그래밍이 적절하다.
<n> = n 개를 팔았을 때 얻을수 있는 최대이익
[n] = n 개를 세트로 팔았을때의 이익
<1> = max([1]) // 한개의 붕어빵은 한가지 방법으로밖에 못 팝니다.
<2> = max([2], [1] + [1])
<3> = max([3], [2] + [1])
<4> = max([4], [3] + [1], [2] + [2])
...
<n> = max([n], [n-1] + [1], ... , [n - j] + [j]) // j 가 n/2 이하인 동안.
위와 같이 1 부터 n 까지 최대이익을 메모해가며 푸는 방식이 DP 이다.
굉장히 어려워 보이는 문제를 쉽게 풀 수 있게 해주는 좋은 방법이다.