백준 DP모음

1947번 [선물 전달]

완전 순열: 일렬로 배열한 대상들의 위치를 재조정했을 때, 모든 대상이 자기 위치에 있지 않도록 하는 배열 방법 

점화식: D[n] = (n-1)(D[n-1] + D[n-2])

ll dp[1000001];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	ll n;
	cin >> n;
	dp[1] = 0;
	dp[2] = 1;
	for (ll i = 3; i <= 1000000; i++) {
		dp[i] = ((i - 1) * (dp[i - 2] + dp[i - 1])) % MOD;
	}
	cout << dp[n];

	return 0;
}

 

13398번 [연속합 2]

수가 하나 제거되면 2부분으로 나뉜다. ㅡ> 2개의 dp배열 사용

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	vector<int> v;
	int left[100001];
	int right[100001];
	
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		v.push_back(x);
	}

	int ans = v[0];
	left[0] = v[0];
	right[n - 1] = v[n - 1];
	for (int i = 1; i < n; i++) {
		left[i] = max(left[i - 1] + v[i], v[i]);
		right[n - 1 - i] = max(right[n - i] + v[n - 1 - i], v[n - 1 - i]);
		if (left[i] > ans) ans = left[i];
		if (right[n - 1 - i] > ans) ans = right[n - 1 - i];
	}
	for (int i = 0; i < n-2; i++) {
		if (left[i] + right[i + 2] > ans) ans = left[i] + right[i + 2];
	}
	cout << ans;
	return 0;
}

 

9252번 [LCS 2]

상황에 따라 점화식 나누기

int dp[1001][1001] = { 0, };
string a, b;

string getLCS(int idx1, int idx2) {
	int len = dp[idx1][idx2];
	if (idx1 == 0 || idx2 == 0) return "";
	if (a[idx1 - 1] == b[idx2 - 1]) {
		if (dp[idx1 - 1][idx2 - 1] == len - 1) {
			return getLCS(idx1 - 1, idx2 - 1) + a[idx1 - 1];
		}
	}
	if (dp[idx1 - 1][idx2] == len) return getLCS(idx1 - 1, idx2);
	else return getLCS(idx1, idx2 - 1);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> a >> b;
	int a_size = a.size();
	int b_size = b.size();

	for (int i = 1; i <= a_size; i++) {
		for (int j = 1; j <= b_size; j++) {
			if (a[i-1] == b[j-1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	cout << dp[a_size][b_size] << "\n" << getLCS(a_size, b_size);

	return 0;
}