다이나믹 프로그래밍

• 큰 문제를 작은 문제로 나눠서 푼다..
• 다음 두 가지 속성을 만족해야 한다.
  (1) Overlapping Subproblem : 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다. 문제를 작은 문제로 쪼갤 수 있다.
  (2) Optimal Substructure : 문제의 정답을 작은 문제의 정답에서 구할 수 있다.
  Optimal Substructure를 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
• 다이나믹 프로그래밍은 (2)를 만족하기 때문에 각 문제를 단 한번만 풀면 된다. 따라서, 정답을 한 번 구했으면 다시 구하지 않도록 메모이제이션을 사용한다.
• Top down 방식은 재귀를 사용하여 푸는 방식이고, Bottom up 방식은 반복문을 사용하여 문제를 푸는 방식이다.
• Top down : 문제를 작은 문제로 나눈 후 작은 문제를 풀고, 작은 문제를 풀었으니 이제 문제를 푼다.
• Bottom up : 문제를 크기가 작은 문제부터 차례대로 푼 후 문제의 크기를 크게 만들어 문제를 푼다.

다이나믹 문제 풀이 전략

• 문제에서 구하려고 하는 답을 문장으로 나타낸다.
• 그 문장에 나와있는 변수의 개수만큼 메모하는 배열을 만든다.
• 문제를 작은 문제로 나누고, 수식을 이용해서 문제를 표현한다.

https://www.acmicpc.net/problem/1463
1로 만들기

D[n] = min(D[n/3], D[n/2], D[n-1]) + 1 // 점화식

top-down 방식

#include <iostream>
#include <cstring>
using namespace std;
int d[1000001];
int go(int n) {
	if (n == 1) {
		return 0;
	}
	if (d[n] > 0) {
		return d[n];
	}
	d[n] = go(n - 1) + 1;
	if (n % 2 == 0) {
		int temp = go(n / 2) + 1;
		if (temp < d[n]) d[n] = temp;
	}
	if (n % 3 == 0) {
		int temp = go(n / 3) + 1;
		if (temp < d[n]) d[n] = temp;
	}
	return d[n];
}
int main() {
	int n;
	cin >> n;
	memset(d, 0, sizeof(d));
	cout << go(n) << '\n';
	return 0;
}

bottom-up 방식

#include <iostream>
#include <cstring>
using namespace std;
int d[1000001];
int main() {
	int n;
	cin >> n;
	memset(d, 0, sizeof(d));
	d[1] = 0;
	for (int i = 2; i <= n; i++) {
		d[i] = d[i - 1] + 1;
		if (i % 2 == 0 && d[i /2] +1 < d[i]) {
			d[i] = d[i / 2] + 1;
		}
		if (i % 3 == 0 && d[i / 3] + 1 < d[i]) {
			d[i] = d[i / 3] + 1;
		}
	}
	cout << d[n] << '\n';
	return 0;
}

https://www.acmicpc.net/problem/11726
2xn 타일링

n-2에 가로 두 개를 더하는 것과 n-1에 세로 한개를 더하는 것으로 풀이가 된다.
n-2에 세로 두개를 더하는 경우는 이미 n-1에 한개를 더하는 것으로 포함이 된다.
D[n] = D[n-1] + D[n-2]

bottom-up

#include <iostream>
#include <cstring>
using namespace std;
int d[1001];
int main() {
	int n;
	cin >> n;
	memset(d, 0, sizeof(d));
	d[1] = 1; d[2] = 2;
	for (int i = 3; i <= n; i++) {
		d[i] = d[i - 2] + d[i - 1];
		d[i] %= 10007;
	}
	cout << d[n] << '\n';
	return 0;
}

top-down

#include <cstdio>
int d[1001];
int go(int n) {
	if (n == 1 || n == 2) {
		return n;
	}
	if (d[n] > 0) {
		return d[n];
	}
	else {
		d[n] = go(n - 1) + go(n - 2);
		return d[n] % 10007;
	}
}
int main() {
	int n;
	scanf("%d", &n);
	int ans = go(n);
	printf("%d\n", ans);
	return 0;
}

https://www.acmicpc.net/problem/11727
2xn 타일링 2

이전 문제에서 + D[n-2]가 추가 되었다. 이는 2x2 사각형을 하나 추가한 것과 같다.
D[n] = D[n-2] * 2 + D[n-1]

#include <iostream>
#include <cstring>
using namespace std;
int d[1001];
int main() {
	int n;
	cin >> n;
	memset(d, 0, sizeof(d));
	d[1] = 1; d[2] = 3;
	for (int i = 3; i <= n; i++) {
		d[i] = d[i - 2] * 2 + d[i - 1];
		d[i] %= 10007;
	}
	cout << d[n] << '\n';
	return 0;
}

https://www.acmicpc.net/problem/9095
1, 2, 3 더하기

D[n] = D[n-3] + D[n-2] + D[n-1]
n-3에 3을 더하는 경우, n-2에 2를 더하는 경우, n-1에 1을 더하는 경우가 있다.

#include <iostream>
#include <cstring>
using namespace std;
int d[12];
int main() {
	int t;
	cin >> t;
	memset(d, 0, sizeof(d));
	while (t--) {
		int n;
		cin >> n;
		d[1] = 1; d[2] = 2; d[3] = 4;
		for (int i = 4; i <= n; i++) {
			d[i] = d[i - 3] + d[i - 2] + d[i - 1];
		}
		cout << d[n] << '\n';
	}
	return 0;
}

https://www.acmicpc.net/problem/15988
1, 2, 3 더하기 3

#include <iostream>
#include <cstring>
using namespace std;
long long d[1000001];
int main() {
	int t;
	cin >> t;
	memset(d, 0, sizeof(d));
	while (t--) {
		int n;
		cin >> n;
		d[1] = 1; d[2] = 2; d[3] = 4;
		for (int i = 4; i <= n; i++) {
			d[i] = d[i - 3] + d[i - 2] + d[i - 1];
			d[i] %= 1000000009;
		}
		cout << d[n] << '\n';
	}
	return 0;
}

https://www.acmicpc.net/problem/11052
카드 구매하기
초기화 할 때 i = 1 부터임에 유의해
i - j + j 를 해야 다시 i가 된다.

#include <iostream>
using namespace std;
int d[1001];
int p[1001];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> p[i];
	}
	d[1] = p[1];
	for (int i = 2; i <= n; i++) {
		d[i] = p[i];
		for (int j = 1; j <= i - 1; j++) {
			if (d[i] < d[i - j] + p[j]) {
				d[i] = d[i - j] + p[j];
			}
		}
	}
	cout << d[n] << '\n';
	return 0;
}

https://www.acmicpc.net/problem/16194
카드 구매하기 2
이전 문제에서 부등호만 바꿔주면 된다.

https://www.acmicpc.net/problem/15990
1, 2, 3 더하기 5
컴퓨터는 이전에 1을 더했는지 2를 더했는지 몰라, 직접 기억 시켜줘야해

#include <iostream>
using namespace std;
long long d[100001][4];
#define mod 1000000009
int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		d[1][1] = 1; d[1][2] = 0; d[1][3] = 0; d[1][0] = 1;
		d[2][1] = 0; d[2][2] = 1; d[2][3] = 0; d[2][0] = 1;
		d[3][1] = 1; d[3][2] = 1; d[3][3] = 1; d[3][0] = 3;
		for (int i = 4; i <= n; i++) {
			d[i][1] = (d[i - 1][2] + d[i - 1][3]) % mod;
			d[i][2] = (d[i - 2][1] + d[i - 2][3]) % mod;
			d[i][3] = (d[i - 3][1] + d[i - 3][2]) % mod;
			d[i][0] = d[i][1] + d[i][2] + d[i][3];
			d[i][0] %= mod;
		}
		cout << d[n][0] << '\n';
	}
	return 0;
}

위의 코드를 개선, 테스트 케이스에 대해 각각 다시 구할 필요가 없다.

#include <iostream>
using namespace std;
long long d[100001][4];
#define mod 1000000009
int main() {
	int t;
	cin >> t;
	d[1][1] = 1; d[1][2] = 0; d[1][3] = 0; d[1][0] = 1;
	d[2][1] = 0; d[2][2] = 1; d[2][3] = 0; d[2][0] = 1;
	d[3][1] = 1; d[3][2] = 1; d[3][3] = 1; d[3][0] = 3;
	for (int i = 4; i <= 100000; i++) {
		d[i][1] = (d[i - 1][2] + d[i - 1][3]) % mod;
		d[i][2] = (d[i - 2][1] + d[i - 2][3]) % mod;
		d[i][3] = (d[i - 3][1] + d[i - 3][2]) % mod;
		d[i][0] = d[i][1] + d[i][2] + d[i][3];
		d[i][0] %= mod;
	}
	while (t--) {
		int n;
		cin >> n;
		cout << d[n][0] << '\n';
	}
	return 0;
}

https://www.acmicpc.net/problem/10844
쉬운 계단 수

#include <iostream>
using namespace std;
#define mod 1000000000
long long d[101][10];
int main() {
	int n;
	cin >> n;
	d[1][0] = 0;
	for (int i = 1; i < 10; i++) {
		d[1][i] = 1;
	}
	for (int i = 2; i <= n; i++) {
		d[i][0] = d[i - 1][1];
		for (int j = 1; j <= 8; j++) {
			d[i][j] = (d[i - 1][j - 1] + d[i - 1][j + 1]) % mod;
		}
		d[i][9] = d[i - 1][8];
	}
	long long ans = 0;
	for (int i = 0; i <= 9; i++) {
		ans += d[n][i];
		ans %= mod;
	}
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/11057
오르막 수

#include <iostream>
using namespace std;
long long d[1001][10];
#define mod 10007
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < 10; i++) {
		d[1][i] = 1;
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			for (int k = j; k >= 0; k--) {
				d[i][j] += d[i - 1][k];
				d[i][j] %= mod;
			}
		}
	}
	long long ans = 0;
	for (int i = 0; i < 10; i++) {
		ans += d[n][i];
		ans %= mod;
	}
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/2193
이친수

#include <iostream>
using namespace std;
long long d[91][2];
int main() {
	int n;
	cin >> n;
	d[1][0] = 0; d[1][1] = 1;
	for (int i = 2; i <= n; i++) {
		d[i][0] = d[i - 1][0] + d[i - 1][1];
		d[i][1] = d[i - 1][0];
	}
	cout << d[n][0] + d[n][1] << '\n';
	return 0;
}