오상우
오상우

Categories

  • algorithm
  • programming

다이나믹 프로그래밍은 사실 다이나믹과는 아무 상관이 없다. 문제를 작게 나누어 답을 저장해가며 큰 문제를 해결하는 문제 해결 방법으로 메모이제이션 프로그래밍으로도 불린다.

백준에서 어떻게 풀어야할지 막막한 문제들은 대개 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 이다.

굉장히 어려워 보이는 문제를 쉽게 풀 수 있게 해주는 좋은 방법이다.