<모든 코드는 C++를 기반으로 작성되었습니다.>

Chapter 8 :: DP

예제 1. 1로 만들기

• 반드시 a 연산을 수행하는 것이 최선은 아니라는 것을 깨닫는게 핵심이다.
• 결국 4가지 연산을 모두 수행해봐야하는데, bruteforce로는 너무 오래걸리므로 dp를 사용하는 것이 유효하다.
• 더 이상 분할할 수 없는 아주 작은 문제부터 반복문을 돌면서 구하고자 하는 큰 문제의 답을 구하는 것이 핵심이다.

#include <iostream>
#include <cstring>
using namespace std;

static int X, dp[30001];

int main() {
	cin >> X;
	for (int i = 2; i <= X; ++i) {
		dp[i] = dp[i - 1] + 1;	// d: X에서 1을 뺸다.
		if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1);	// c: 2로 나눈다.
		if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1);	// b: 3으로 나눈다.
		if (i % 5 == 0) dp[i] = min(dp[i], dp[i / 5] + 1);	// a: 5로 나눈다.
	}
	cout << dp[X] << '\n';
}

• 외부에 dp배열을 만들고, i = 2부터 시작해서 문제의 크기를 늘려나간다.
• 4가지 연산을 모두 수행하면서 최소 연산 회수를 저장한다.

예제 2. 개미 전사

• 점화식을 세워서 재귀를 돌리는 전형적인 DP 문제다.
• n-2번째 식량 창고를 턴다면, n번째 식량 창고를 털 수 있고,
  n-1번째 식량 창고를 턴다면, n번째 식량 창고를 털 수 없다.
• 그러므로, $D(n) = max(D(n-1), D(n-2) + arr(n))$ 이라는 점화식을 구할 수 있다.

#include <iostream>
using namespace std;

static int N, food[101], cache[101];

int solve(int n) {
	if (n <= 0) return 0;
	if (cache[n] > 0) return cache[n];
	return cache[n] = max(solve(n - 1), solve(n - 2) + food[n]); // 점화식 그대로 사용
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; ++i) cin >> food[i];
	cout << solve(N) << '\n';
}

예제 3. 바닥 공사

• 점화식을 세워서 재귀를 돌리는 전형적인 DP 문제다.
• n번째 열을 채우는 경우의 수는
  n-1번째 열까지 채우고, $2 \times 1$ 타일을 하나 사용하는 경우와
  n-2번째 열까지 채우고, $1 \times 2$ 타일 2개 사용하는 경우, $2 \times 2$ 타일 1개를 사용하는 경우가 있다.
• 따라서, $D(n) = D(n-1) + 2 \times D(n-2)$이다.

#include <iostream>
using namespace std;

static int N, dp[1001] = {0, 1, 3, };

int solve(int n) {
	if (n <= 0) return 0;
	if (dp[n] > 0) return dp[n];
	return dp[n] = (solve(n - 1) + solve(n - 2) * 2) % 796796;
}

int main() {
	cin >> N;
	cout << solve(N) << '\n';
}

예제 4. 효율적인 화폐 구성

#include <iostream>
#include <cstring>
using namespace std;

static int N, M, coin[101], dp[10001];

int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; ++i) cin >> coin[i];
	memset(dp, 10001, sizeof(dp));	// 초기화, 10001을 넘을 수 없다.
	dp[0] = 0;
	for (int i = 1; i <= N; ++i)			// 모든 코인에 대해 검사한다.
		for (int j = coin[i]; j <= M; ++j)	// 모든 금액에 대해 검사한다.
			dp[j] = min(dp[j], dp[j - coin[i]] + 1);
	if (dp[M] <= M) cout << dp[M] << '\n';	// 정상 범주라면 답 출력.
	else cout << -1 << '\n';				// 비정상 범주라면 불가능이라 판단.
}