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

https://www.acmicpc.net/problem/9465
스티커
뒤에서 어떻게 변할지 모르기 때문에 실시간으로 비교가 불가능 -> 모두 저장

#include <iostream>
#include <algorithm>
using namespace std;
long long d[100001][3];
int a[100001][3];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		for (int i = 1; i <= 2; i++) {
			for(int j = 1; j<=n; j++){
				cin >> a[j][i];
			}
		}
		d[1][0] = 0;
		d[1][1] = a[1][1];
		d[1][2] = a[1][2];
		for (int i = 2; i <= n; i++) {
			d[i][0] = max(max(d[i - 1][0], d[i - 1][1]), d[i - 1][2]);
			d[i][1] = max(d[i - 1][0], d[i - 1][2]) + a[i][1];
			d[i][2] = max(d[i - 1][0], d[i - 1][1]) + a[i][2];
		}
		cout << max({ d[n][0], d[n][1], d[n][2] }) << '\n';
	}
	return 0;
}

https://www.acmicpc.net/problem/2156
포도주 시식
max에 d[i-1][0]을 반드시 추가해야 하는 이유 - oox가 xoo, oxo보다 클 수 있음

#include <cstdio>
#include <algorithm>
using namespace std;
int d[10001][3];
int a[10001];
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	if (n == 1) {
		printf("%d\n", a[1]);
		return 0;
	}
	d[2][0] = a[1];
	d[2][1] = a[2];
	d[2][2] = a[1] + a[2];
	for (int i = 3; i <= n; i++) {
		d[i][2] = d[i - 1][1] + a[i];
		d[i][1] = d[i - 1][0] + a[i];
		d[i][0] = max(d[i - 1][0], max(d[i - 1][1], d[i - 1][2]));
	}
	int ans = 0;
	ans = max(d[n][0], max(d[n][1], d[n][2]));
	printf("%d\n", ans);
	return 0;
}

https://www.acmicpc.net/problem/11053
가장 긴 증가하는 부분 수열

어디서부터 시작해야하는지 몰라 -> 각 인덱스에서 각각의 최대 값 저장

#include <iostream>
#include <algorithm>
using namespace std;
int a[1001];
int d[1001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	d[1] = 1;
	for (int i = 2; i <= n; i++) {
		d[i] = 1;
		for (int j = 1; j < i; j++) {
			if (a[j] < a[i] && d[i] < d[j] + 1) {
				d[i] = d[j] + 1;
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (ans < d[i]) ans = d[i];
	}
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/14002
가장 긴 증가하는 부분 수열 4

reverse를 쓴 경우

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int a[1001];
int d[1001];
int prev_index[1001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	d[1] = 1;
	prev_index[1] = 0;
	for (int i = 2; i <= n; i++) {
		d[i] = 1;
		prev_index[i] = 0;
		for (int j = 1; j < i; j++) {
			if (a[j] < a[i] && d[i] < d[j] + 1) {
				d[i] = d[j] + 1;
				prev_index[i] = j;
			}
		}
	}
	int max = 0;
	int index = 1;
	for (int i = 1; i <= n; i++) {
		if (max < d[i]) {
			max = d[i];
			index = i;
		}
	}
	cout << max << '\n';
	vector<int> re;
	re.push_back(index);
	while (prev_index[index]) {
		re.push_back(prev_index[index]);
		index = prev_index[index];
	}
	reverse(re.begin(), re.end());
	for (int i = 0; i < re.size(); i++) {
		cout << a[re[i]] << ' ';
	}
	cout << '\n';
	return 0;
}

재귀로 프린트하는 경우

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int a[1001];
int d[1001];
int prev_index[1001];
void go(int index) {
	if (index == 0) return;
	go(prev_index[index]);
	cout << a[index] << ' ';
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	d[1] = 1;
	prev_index[1] = 0;
	for (int i = 2; i <= n; i++) {
		d[i] = 1;
		prev_index[i] = 0;
		for (int j = 1; j < i; j++) {
			if (a[j] < a[i] && d[i] < d[j] + 1) {
				d[i] = d[j] + 1;
				prev_index[i] = j;
			}
		}
	}
	int max = 0;
	int index = 0;
	for (int i = 1; i <= n; i++) {
		if (max < d[i]) {
			max = d[i];
			index = i;
		}
	}
	cout << max << '\n';
	go(index);
	cout << '\n';
	return 0;
}

https://www.acmicpc.net/problem/11055
가장 큰 증가 부분 수열

#include <iostream>
#include <algorithm>
using namespace std;
int d[1001];
int a[1001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	d[1] = a[1];
	for (int i = 2; i <= n; i++) {
		d[i] = a[i];
		for (int j = 1; j < i; j++) {
			if (a[j] < a[i] && d[i] < d[j] + a[i]) {
				d[i] = d[j] + a[i];
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (ans < d[i]) ans = d[i];
	}
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/11722
가장 긴 감소하는 부분 수열

#include <iostream>
#include <algorithm>
using namespace std;
int d[1001];
int a[1001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	d[1] = 1;
	for (int i = 2; i <= n; i++) {
		d[i] = 1;
		for (int j = 1; j < i; j++) {
			if (a[j] > a[i] && d[i] < d[j] + 1) {
				d[i] = d[j] + 1;
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (ans < d[i]) ans = d[i];
	}
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/11054
가장 긴 바이토닉 부분 수열

Devide and Conquer

#include <iostream>
#include <algorithm>
using namespace std;
int d[1001][2];
int a[1001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	// 왼쪽에서 시작
	d[1][0] = 1;
	for (int i = 2; i <= n; i++) {
		d[i][0] = 1;
		for (int j = 1; j < i; j++) {
			if (a[j] < a[i] && d[i][0] < d[j][0] + 1) {
				d[i][0] = d[j][0] + 1;
			}
		}
	}
	d[n][1] = 1;
	for (int i = n - 1; i >= 1; i--) {
		d[i][1] = 1;
		for (int j = n; j > i; j--) {
			if (a[j] < a[i] && d[i][1] < d[j][1] + 1) {
				d[i][1] = d[j][1] + 1;
			}
		}
	}


	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (ans < d[i][0] + d[i][1] - 1) ans = d[i][0] + d[i][1] - 1;
	}
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/1912
연속합

#include <iostream>
#include <algorithm>
using namespace std;
int a[100001];
int d[100001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	d[1] = a[1];
	for (int i = 2; i <= n; i++) {
		d[i] = a[i];
		if (d[i] < d[i - 1] + a[i]) d[i] = d[i - 1] + a[i];
	}
	int ans = -2000;
	for (int i = 1; i <= n; i++) {
		if (ans < d[i]) ans = d[i];
	}
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/13398
연속합 2

Devide and Conquer

#include <iostream>
#include <algorithm>
using namespace std;
int a[100001];
int dl[100001];
int dr[100001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	dl[1] = a[1];
	for (int i = 2; i <= n; i++) {
		dl[i] = a[i];
		if (dl[i] < dl[i - 1] + a[i])
			dl[i] = dl[i - 1] + a[i];
	}
	dr[n] = a[n];
	for (int i = n - 1; i > 0; i--) {
		dr[i] = a[i];
		if (dr[i] < dr[i + 1] + a[i])
			dr[i] = dr[i + 1] + a[i];
	}
	int ans = dl[1];
	for (int i = 2; i <= n; i++) {
		if (ans < dl[i]) ans = dl[i];
	}
	for (int i = 2; i <= n - 1; i++) {
		if (ans < dl[i - 1] + dr[i + 1])
			ans = dl[i - 1] + dr[i + 1];
	}
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/1699
제곱수의 합

제곱 수 일때 d[i] = d[0] + 1 = 1;

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

https://www.acmicpc.net/problem/2225
합분해
단순하게 생각하기, 안에 숫자들이 어떻게 생겼는지 묻는게 아니라,
단순히 갯수만 물어보는 것임. 이는 다이나믹으로
D[k][n] = 시그마{D[k-1][n-L]}, 0 <= L <= n

#include <iostream>
using namespace std;
long long d[201][201];
#define mod 1000000000
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	d[0][0] = 1LL;
	for (int i = 1; i <= k; i++) {
		for (int j = 0; j <= n; j++) {
			for (int l = 0; l <= j; l++) {
				d[i][j] += d[i - 1][j - l];
				d[i][j] %= mod;
			}
		}
	}
	cout << d[k][n] << '\n';
	return 0;
}