https://www.acmicpc.net/problem/2293 [ 풀이 법 ] k원을 만드는 경우의 수는 아래의 그림과 같습니다. [ 그림 1. k원을 만드는 경우의 수 ] 우선, 위의 배열은 어떤 금액을 만드는 경우의 수입니다. 배열이름을 dp라고 하겠습니다. 그러면 dp(k)는 k원을 만드는 경우의 수입니다. 그리고 Cn은 n번째 동전의 가치입니다. 위의 예제 입력에서 C1은 1, C2는 2, C3은 5입니다. 그럼, 이런 식의 점화식이 가능합니다. dp( n, k ) = dp( n, k - Cn ) + dp( n - 1, k ) 이 점화식에서 dp( n, k )는 n개의 동전으로 k원을 만드는 경우의 수입니다. 그러므로 dp( n, k - Cn )은 n개의 동전으로 k - Cn을 만드는 경우의 ..
https://www.acmicpc.net/problem/1932 [ 문제 풀이 법 ]다이나믹 프로그래밍은 bottom-up방식으로 밑에서 위로 올라가는 방식이다. 분할정복법과 대조된다.문제풀이법을 살펴보자. 임의의 원소까지의 최대값은 어떻게 될까? 위 예제에서 3행 2열의 값인 1을 임의의 원소로 잡고 여기까지의 최대값은 무엇일까? 최대값을 배열 DP에 저장한다.아마 대답을 이렇게 미룰 수 있을 것이다. 3행 2열을 오기 바로 전의 최대값 + 3행 2열의 값.의문은 3행 2열 바로 전까지의 최대값을 바로 알 수 가없다. 그런데, (1, 1)부터 시작하면, 최대값을 하나씩 쌓아갈 수 있다. 그래서 다이나믹 프로그래밍이 bottom-up방식의 문제해결법인 것이다.3행 2열 바로 전까지의 최대값의 후보는 2..