다이나믹 프로그래밍 (3)

https://www.acmicpc.net/problem/11048
이동하기

왜 다이나믹으로 풀어야 하는가?
문제가 다이나믹의 조건을 만족하는가?
(1) Overlapping subploblem

• 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.
• 큰 문제를 작은 문제로 쪼갤 수 있다.
  (2) Optimal substructure
• 문제의 정답을 작은 문제의 정답에서 구할 수 있다. (Memoization)

해당 문제는 항상 아래, 오른쪽, 아래 + 오른쪽으로만 갈 수 있고 최종 목적지는
최 하단 최 우측이다. 따라서 현재 칸을 기준으로 위, 왼쪽, 위 + 왼쪽 칸 중 가장 큰 값을
이용하여 현재 칸까지의 합의 최대 값을 구하면 된다. 이는 (1)과 (2)의 조건을 만족한다.

방법 1

#include <iostream>
#include <algorithm>
using namespace std;
int a[1001][1001];
int d[1001][1001];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			d[i][j] = max({ d[i - 1][j - 1], d[i - 1][j],
				d[i][j - 1] }) + a[i][j];

		}
	}
	cout << d[n][m] << '\n';
	return 0;
}

방법 2 - 대각선 이동을 처리하지 않아도 된다. 대각선 이동은 다른 2가지 방법보다 작거나 같기 때문이다.(음수가 없기 때문에)

#include <iostream>
#include <algorithm>
using namespace std;
int a[1001][1001];
int d[1001][1001];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			d[i][j] = max(d[i-1][j], d[i][j-1]) + a[i][j];

		}
	}
	cout << d[n][m] << '\n';
	return 0;
}

방법 3 - top down 방식

• 메모이제이션을 불러오는 방식
• 언제 종료해야 할지

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;
int a[1001][1001];
int d[1001][1001];
int go(int i, int j) {
	if (i < 1 || j < 1) {
		return 0;
	}
	if (d[i][j] >= 0) return d[i][j];
	d[i][j] = max(go(i - 1, j), go(i, j - 1)) + a[i][j];
	return d[i][j];
}
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	memset(d, -1, sizeof(d));
	cout << go(n, m) << '\n';
	return 0;
}

방법 4 - top down 2

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;
int a[1001][1001];
int d[1001][1001];
int n, m;
int go(int i, int j) {
	if (n < i || m < j) {
		return 0;
	}
	if (d[i][j] >= 0) return d[i][j];
	d[i][j] = max(go(i + 1, j), go(i, j + 1)) + a[i][j];
	return d[i][j];
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	memset(d, -1, sizeof(d));
	cout << go(1, 1) << '\n';
	return 0;
}

https://www.acmicpc.net/problem/1890
점프

long long 주의, 문제 제대로 읽기

bottom up

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long a[101][101];
long long d[101][101];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	d[1][1] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int r = 1; r < i; r++) {
				if (r + a[r][j] == i) {
					d[i][j] += d[r][j];
				}
			}
			for (int c = 1; c < j; c++) {
				if (c + a[i][c] == j) {
					d[i][j] += d[i][c];
				}
			}
		}
	}
	cout << d[n][n] << '\n';
	return 0;
}

top down

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long a[101][101];
long long d[101][101];
long long go(int n, int m) {
	if (d[n][m] > 0) return d[n][m];
	for (int i = n - 1; i > 0; i--) {
		if (i + a[i][m] == n) {
			d[n][m] += go(i, m);
		}
	}
	for (int j = m - 1; j > 0; j--) {
		if (j + a[n][j] == m) {
			d[n][m] += go(n, j);
		}
	}
	return d[n][m];
}
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
			d[i][j] = 0;
		}
	}
	d[1][1] = 1;
	cout << go(n, n) << '\n';
	return 0;
}

n^3에서 n^2로 줄이는 방법

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long a[101][101];
long long d[101][101];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
			d[i][j] = 0;
		}
	}
	d[1][1] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (a[i][j] == 0) continue;
			if (i + a[i][j] <= n) {
				d[i + a[i][j]][j] += d[i][j];
			}
			if (j + a[i][j] <= n) {
				d[i][j + a[i][j]] += d[i][j];
			}
		}
	}
	cout << d[n][n] << '\n';
	return 0;
}

https://www.acmicpc.net/problem/10942
팰린드롬?

top down

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[2001];
int d[2001][2001];
int go(int i, int j) {
	if (i == j) return 1;
	if (j - i == 1) {
		if (a[i] == a[j]) return 1;
		else return 0;
	}
	if (d[i][j] != -1) return d[i][j];
	if (a[i] != a[j])  d[i][j] = 0;
	else {
		d[i][j] = go(i + 1, j - 1);
	}
	return d[i][j];
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	memset(d, -1, sizeof(d));
	int m;
	cin >> m;
	while (m--) {
		int s, e;
		cin >> s >> e;
		cout << go(s, e) << '\n';
	}
	return 0;
}

bottom up

#include <iostream>
using namespace std;
int a[2001];
int d[2001][2001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		d[i][i] = 1;
	}
	for (int i = 1; i < n; i++) {
		if (a[i] == a[i + 1]) d[i][i + 1] = 1;
	}
	for (int k = 3; k <= n; k++) {
		for (int i = 1; i <= n - k + 1; i++) {
			int j = i + k - 1;
			if (a[i] == a[j] && d[i + 1][j - 1]) {
				d[i][j] = 1;
			}
		}
	}
	int m;
	cin >> m;
	while (m--) {
		int s, e;
		cin >> s >> e;
		cout << d[s][e] << '\n';
	}
	return 0;
}

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

bottom up

#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;
}

top down

#include <iostream>
#include <algorithm>
using namespace std;
int d[12];
int go(int n) {
	if (n < 1) return 0;
	if (d[n] > 0) return d[n];
	d[n] = go(n - 1) + go(n - 2) + go(n - 3);
	return d[n];
}
int main() {
	int t;
	cin >> t;
	d[1] = 1; d[2] = 2; d[3] = 4;
	while (t--) {
		int n;
		cin >> n;
		cout << go(n) << '\n';
	}
	return 0;
}

https://www.acmicpc.net/problem/15989
1,2,3 더하기 4
1이 뒤에 붙는 걸 먼저 만들어 놓고
2가 뒤에 붙는 걸 만든 후,
최종 적으로 3이 뒤에 붙는 걸 만든다.

#include <stdio.h>
long long d[1000001];
const long long mod = 10009LL;
const int limit = 100000;
int main() {
    d[0] = 1;
    for (int i = 1; i <= limit; i++) {
        if (i - 1 >= 0) {
            d[i] += d[i - 1];
        }
    }
    for (int i = 1; i <= limit; i++) {
        if (i - 2 >= 0) {
            d[i] += d[i - 2];
        }
    }
    for (int i = 1; i <= limit; i++) {
        if (i - 3 >= 0) {
            d[i] += d[i - 3];
        }
    }
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        printf("%lld\n", d[n]);
    }
}