dp with 포함배제 원리

포함배제 원리를 이용하는 dp문제 2개를 풀어보자. 

1. BOJ 14517 

https://www.acmicpc.net/problem/14517

14517번: 팰린드롬 개수 구하기 (Large)

[ 풀이 ]

문제를 잘 이해해야 한다. 부분수열이므로 연속된 팰린드롬일 필요가 없다. 

맨처음과 끝에서 시작해서 좁혀가면서 갱신해주면 된다. 

dp[s][e]:=구간 [s,e]를 볼 때 팰린드롬의 총 개수라고 정의하면, 상태전이는 3가지가 있다. 

1. s를 사용안하고 [s+1,e]로 전이

2. e를 사용안하고 [s, e-1]로 전이

3. s, e를 사용안하고 [s+1, e-1]로 전이

4. s와 e 문자가 같다면 둘다 사용하고 [s+1,e-1]로 전이

이 때, 1번과 2번을 세면서 3번이 중복해서 세짐을 알 수 있다. 

따라서 1번 빼준다는게 이 점화식의 핵심이다. 

 

[ Code ]

#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001], mod = 10007;
string str;

// dp[s][e]: [s, e] #palindrome 
int go(int s, int e) {
	if (s > e) return 0; // base 
	if (s == e) return 1; // base 
	int& ret = dp[s][e];
	if (~ret) return ret;
	// CASE1 + CASE2 - CASE3
	ret = (go(s + 1, e) + go(s, e - 1) - go(s + 1, e - 1) + mod) % mod;
	// if palindrome.. 
	if (str[s] == str[e]) ret = (ret + 1 + go(s + 1, e - 1)) % mod;
	return ret;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> str;
	memset(dp, -1, sizeof(dp));
	// answer 
	cout << go(0, str.length() - 1);
}

 

---

 

2. BOJ 14165 

https://www.acmicpc.net/problem/14165

14165번: Team Building

[ 풀이 ] 

크기순으로 매칭할꺼고 순서는 상관없으므로 정렬해놓고 시작하자. 

dp를 어떻게 만들건지는 쉽다. FJ와 FP가 모두 몇번 인덱스까지 봤을 때 길이가 얼마인지 대충 이정도 정보가 필요하다.

dp[i][j][k]:= FJ가 i번을 볼 것이고, FP가 j번을 볼 것이고 현재 만들어진 길이가 k가 되는 경우의 수라고 하자. 

식 세울때 미세한 팁이 있다면, 전이시키는 점화식의 특징은 항상 현재값을 그냥 안쓰고 다음으로 넘겨주는게

대부분 들어가게 된다. 

전이는 4가지가 있다. 

1. i를 사용안하고 i+1, j, k로 전이

2. j를 사용안하고 i, j+1, k로 전이

3.  i,j를 사용안하고 i+1, j+1, k로 전이

4.   i,j를 사용하고 i+1, j+1, k+1로 전이

여기서 1,2를 셀 때 3은 중복해서 세진다. 마찬가지로 1번 빼주고 점화식을 완성시켜주면 된다. 

 

[ Code ]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, k, a[1001], b[1001], dp[1001][1001][11];
const ll mod = 1e9 + 9;

ll go(int i, int j, int len) {
	if (len == k) return 1; // base case
	if (i == n + 1 || j == m + 1) return len == k; // 1개가 먼저 끝났을 때 
	ll& ret = dp[i][j][len];
	if (~ret) return ret;
	// CASE1+CASE2-CASE3
	ret = (go(i + 1, j, len) + go(i, j + 1, len) - go(i + 1, j + 1, len) + mod) % mod;
	// CASE4
	if (a[i] > b[j]) ret = (ret + go(i + 1, j + 1, len + 1)) % mod;
	return ret;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++) cin >> b[i];
	sort(a + 1, a + n + 1);
	sort(b + 1, b + m + 1);
	memset(dp, -1, sizeof(dp));
	cout << go(1, 1, 0) << '\n';
}