ALOHA 월반 4주차 - DP (Interval DP / LIS / LCS)

ALOHA - 2022/ALOHA - 초급반 → 중급반 월반 (2022 여름방학) 2022. 8. 19. 18:06

1. [22971] 증가하는 부분 수열의 개수 (Silver II)

의도한 태그: Longest Increasing Subsequence

$D_{i} = A_{i}$ 로 끝나는 LIS의 개수를 정의하면, 점화식은 아래와 같이 적어볼 수 있습니다.

$j < i$ 면서 $A_{j} < A_{i}$ 인 $j$ 에 대해, $\sum D_{j}$

const ll mod= 998244353;
int arr[5020];
ll dp[5020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i <= n; i++){
		dp[i] = 1;
		for (int j = 1; j < i; j++){
			if (arr[j] >= arr[i]){ continue; }
			dp[i] += dp[j]; dp[i] %= mod;
		}
	}
	for (int i = 1; i <= n; i++){ cout << dp[i] << ' '; }
}

2. [2565] 전깃줄 (Gold V)

의도한 태그: Longest Increasing Subsequence

왼쪽에서 $i$ 번에 연결된 전깃줄이 오른쪽에서는 $A_{i}$ 번에 연결되어있다고 해봅시다.

그럼, 두 전깃줄이 교차하지 않는다는 건 $i < j$ 면 $A_{i} < A_{j}$ 라는 의미가 됩니다.

그럼 최대한 많은 전깃줄을 남기려면, $i < j$ 면서 $A_{i} < A_{j}$ 인 $A_{i}$ 를 최대한 길게 해야 하므로

이 문제는 그냥 LIS를 구하는 문제가 됩니다.

const int N = 500;
int arr[520], dp[520];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		int a, b; cin >> a >> b; arr[a] = b;
	}
	int ans = 0;
	for (int i = 1; i <= N; i++){
		if (arr[i] == 0){ continue; }
		dp[i] = 1;
		for (int j = 1; j < i; j++){
			if (arr[j] == 0){ continue; }
			if (arr[j] < arr[i]){ dp[i] = max(dp[i], dp[j]+1); }
		}
		ans = max(ans, dp[i]);
		//cout << arr[i] << " | DP " << i << " = " << dp[i] << endl;
	}
	cout << n-ans;
}

3. [25343] 최장 최장 증가 부분 수열 (Gold V)

의도한 태그: Longest Increasing Subsequence

$D_{y, x} = (y, x)$ 를 끝으로 하는 LIS의 최대 길이 를 정의해봅시다.

그럼, 점화식은 아래 값들의 최댓값이 됩니다. (기본값 = 1)

$i < y, j < x$ 에 대해 $A_{i, j} < D_{y, x}$ 라면: $D_{i, j} + 1$

문제의 답은 $max_{1 \leq x, y \e N} D_{y, x}$ 가 됩니다.

+ 시간복잡도는 $O (N^{4})$ 이지만, 실제로는 $O (N^{4} / 4)$ 에 가까워서 2500만 회의 연산으로 AC를 받을 수 있습니다.

int arr[120][120], dp[120][120];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){ cin >> arr[i][j]; }
	}
	int ans = 0;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			int mx = 0;
			for (int y = 1; y <= i; y++){
				for (int x = 1; x <= j; x++){
					if (arr[y][x] < arr[i][j]){ mx = max(mx, dp[y][x]); }
				}
			}
			dp[i][j] = mx+1; ans = max(ans, dp[i][j]);
		}
	}
	cout << ans;
}

4. [9252] LCS 2 (Gold IV)

의도한 태그: Longest Common Substring

$D_{i, j} = S_{1}$ 의 첫 $i$ 글자와 $S_{2}$ 의 첫 $j$ 글자로 만들 수 있는 LCS의 길이 를 정의해봅시다.

그럼, 점화식은 아래와 같이 나오게 됩니다.

$S_{1}$ 의 $i$ 번째 글자를 무시하고 LCS를 구해보기: $D_{i - 1, j}$
$S_{2}$ 의 $j$ 번째 글자를 무시하고 LCS를 구해보기: $D_{i, j - 1}$
$S_{1}$ 의 $i$ 번째 글자와 $S_{2}$ 의 $j$ 번째 글자를 LCS에 매칭시켜보기: $D_{i - 1, j - 1} + 1$
- 이 경우는 $S_{1, i} = S_{2, j}$ 여야 합니다.

위 3가지 경우 중 가장 큰 값을 들고 오면 점화식이 완성됩니다.

초항은, 한 쪽 문자열이 비어있을 때 $D_{0, i} = D_{i, 0} = 0$ 이고,

문제의 답은 $D_{| S_{1} |, | S_{2} |}$ 가 됩니다.

그럼 실제 LCS는 어떻게 구할까요?

우선 $p_{1}, p_{2}$ 를 준비한 뒤, 아래와 같이 역추적을 돌려주면 됩니다.

$S_{1, p_{1}} = S_{2, p_{2}} and D_{p_{1} - 1, p_{2} - 1} + 1$ : LCS의 맨 앞에 $S_{1, p_{1}}$ 를 추가 후, $p_{1}, p_{2}$ 를 각각 1씩 감소
그 외의 경우: $D_{p_{1} - 1, p_{2}}$ 와 $D_{p_{1}, p_{2} - 1}$ 중 더 큰 값을 가지고 있는 상태로 가면 됩니다.

int dp[1020][1020];

void Main(){
	string s1, s2; cin >> s1 >> s2; int l1 = s1.size(), l2 = s2.size();
	s1 = " " + s1; s2 = " " + s2;
	for (int i1 = 1; i1 <= l1; i1++){
		for (int i2 = 1; i2 <= l2; i2++){
			dp[i1][i2] = max(dp[i1-1][i2], dp[i1][i2-1]);
			if (s1[i1] == s2[i2]){ dp[i1][i2] = max(dp[i1][i2], dp[i1-1][i2-1] + 1); }
		}
	}
	cout << dp[l1][l2] << endl;
	int p1 = l1, p2 = l2; stack<char> stk;
	while (p1 > 0 && p2 > 0){
		if (s1[p1] == s2[p2] && dp[p1-1][p2-1]+1 == dp[p1][p2]){
			stk.push(s1[p1]); p1 -= 1; p2 -= 1;
		}
		else{
			if (dp[p1-1][p2] > dp[p1][p2-1]){ p1 -= 1; }
			else{ p2 -= 1; }
		}
	}
	while (!stk.empty()){ cout << stk.top(); stk.pop(); }
}

5. [11066] 파일 합치기 (Gold III)

의도한 태그: Interval DP

$D_{s t, e d} = [s t, e d]$ 구간의 파일을 하나로 합치는데 드는 총 비용 을 정의해봅시다.

그럼 점화식은 아래와 같이 계산해볼 수 있습니다.

$[s t, s t]$ 를 합치고 $[s t + 1, e d]$ 를 합친 뒤, 이 두 파일을 합치기: $D_{s t, s t} + D_{s t + 1, e d} + \sum_{i = s t}^{s t} A_{i} + \sum_{i = s t + 1}^{e d} A_{i}$
$[s t, s t + 1]$ 을 합치고 $[s t + 2, e d]$ 를 합친 뒤, 이 두 파일을 합치기: $D_{s t, s t + 1} + D_{s t + 2, e d} + \sum_{i = s t}^{s t + 1} A_{i} + \sum_{i = s t + 2}^{e d} A_{i}$
...
$[s t, e d - 1]$ 을 합치고 $[e d, e d]$ 를 합친 뒤, 이 두 파일을 합치기: $D_{s t, e d - 1} + D_{e d, e d} + \sum_{i = s t}^{e d - 1} A_{i} + \sum_{i = e d}^{e d} A_{i}$

물론 저걸 저대로 구현하라고 하면 하기 싫을테니, 이를 간단하게 바꿔봅시다.

우선, 위 점화식을 아래와 같이 나타내볼 수 있습니다.

$min_{s t \leq k < e d} (D_{s t, k} + D_{k + 1, e d} + \sum_{i = s t}^{k} A_{i} + \sum_{i = k + 1}^{e d} A_{i})$

그런데 수열에서 $\sum_{i = s t}^{k} A_{i} + \sum_{i = k + 1}^{e d} A_{i} = \sum_{i = s t}^{e d} A_{i}$ 이므로,

$min_{s t \leq k < e d} (D_{s t, k} + D_{k + 1, e d} + \sum_{i = s t}^{e d} A_{i})$ 으로 줄여써볼 수 있습니다.

물론 구간의 합을 구하는 건 시간이 오래 걸리니, 실제로는 누적합으로 빠르게 구해주면 됩니다.

초항은 간단하게 $D_{i, i} = 0$ 이고, 문제의 답은 $D_{1, N}$ 이 됩니다.

const ll INF = 1e15;
ll arr[520], prf[520]; ll dp[520][520];
inline ll sum(int st, int ed){ return prf[ed] - prf[st-1]; }

void Main(){
	int t; cin >> t;
	while (t--){
		int n; cin >> n;
		for (int i = 1; i <= n; i++){ cin >> arr[i]; }
		for (int i = 1; i <= n; i++){ prf[i] = prf[i-1] + arr[i]; }
		for (int l = 2; l <= n; l++){
			for (int st = 1; ; st++){
				int ed = st+l-1; if (ed > n){ break; }
				dp[st][ed] = INF; ll val = sum(st, ed);
				for (int k = st; k < ed; k++){
					dp[st][ed] = min(dp[st][ed], dp[st][k]+dp[k+1][ed] + val);
				}
			}
		}
		cout << dp[1][n] << endl;
	}
}

6. [1958] LCS 3 (Gold III)

의도한 태그: Longest Common Substring

$D_{i, j, k} = S_{1}$ 의 첫 $i$ 글자, $S_{j}$ 의 첫 $j$ 글자, $S_{k}$ 의 첫 $k$ 글자로 만들 수 있는 최대 LCS 를 정의해봅시다.

그럼, 점화식은 아래와 같은 경우에 대한 값의 최대가 됩니다.

$S_{1}$ 의 $i$ 번째 글자를 무시: $D_{i - 1, j, k}$
$S_{2}$ 의 $j$ 번째 글자를 무시: $D_{i, j - 1, k}$
$S_{3}$ 의 $k$ 번째 글자를 무시: $D_{i, j, k - 1}$
$S_{1, i} = S_{2, j} = S_{3, k}$ 라면, 저 글자를 원래 LCS에 추가: $D_{i - 1, j - 1, k - 1} + 1$

초항은 $D_{0, j, k} = D_{i, 0, k} = D_{i, j, 0} = 0$ 이고, 답은 $D_{| S_{1} |, | S_{2} |, | S_{3} |}$ 이 됩니다.

int dp[120][120][120];

void Main(){
	string s1, s2, s3;
	cin >> s1 >> s2 >> s3;
	int l1 = s1.size(), l2 = s2.size(), l3 = s3.size();
	for (int i = 0; i <= l1; i++){
		for (int j = 0; j <= l2; j++){
			for (int k = 0; k <= l3; k++){
				if (i*j*k == 0){ dp[i][j][k] = 0; }
				else{
					dp[i][j][k] = max({ dp[i][j][k-1], dp[i][j-1][k], dp[i-1][j][k] });
					if (s1[i-1] == s2[j-1] && s2[j-1] == s3[k-1]){
						dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-1]+1);
					}
				}
			}
		}
	}
	cout << dp[l1][l2][l3];
}

7. [24940] Split the GSHS (Gold III)

의도한 태그: Interval DP

$D_{s t, e d} = [s t . e d]$ 구간의 학생들을 합치면서 떨어뜨릴 수 있는 친밀도 를 정의해봅시다.

그럼 점화식은 $s t \leq k < e d$ 인 $k$ 에 대해 아래 값의 최대가 됩니다.

$[s t, k]$ 를 합친 뒤, $(k, e d]$ 를 합치고, 이 둘을 합치기: $D_{s t, k} + D_{k + 1, e d} + f ([s t, k], [k + 1, e d])$
- 여기서 함수 $f$ 는 두 학생 무리를 합칠 때 감소시킬 수 있는 친밀도입니다.

초항은 $D_{i, i} = 0$ 이고, 문제의 답은 $D_{1, N}$ 이 됩니다.

ll arr[90], prf[90];
ll dp[90][90];

int sgn(ll x){ return (x > 0) - (x < 0); }
ll sum(int st, int ed){ return prf[ed] - prf[st-1]; }

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i <= n; i++){ prf[i] = prf[i-1] + arr[i]; }
	for (int len = 2; len <= n; len++){
		for (int st = 1, ed = len; ed <= n; st++, ed++){
			for (int k = st; k < ed; k++){
				ll res = dp[st][k] + dp[k+1][ed];
				if (sgn(sum(st, k)) != sgn(sum(k+1, ed))){
					res -= sum(st, k) * sum(k+1, ed);
				}
				dp[st][ed] = max(dp[st][ed], res);
			}
			//cout << "DP " << st << ' ' << ed << " = " << dp[st][ed] << endl;
		}
	}
	cout << -dp[1][n];
}

8. [7476] 최대 공통 증가 수열 (Gold I)

의도한 태그: Longest Common Substring, Longest Increasing Subsequence

우선 $i$ 가 증가하는 순서대로 스위핑을 날리면서, 전역으로 아래 DP를 업데이트해봅시다.

$D_{j} = B_{j}$ 를 끝으로 하는 LCIS의 최대 길이 (초기값 = 0)

그럼, 아래와 같이 DP를 업데이트해볼 수 있습니다.

$A_{i} = B_{j}$ 라면, $k < j$ 이고 $B_{k} < B_{j}$ 인 $k$ 에 대해 $D_{j}$ 를 $D_{k} + 1$ 로 업데이트

역추적은 $P_{j, c} = B_{j}$ 를 끝으로 하는 길이 $c$ 의 LCIS에서, $B_{j}$ 직전에 나오는 원소(의 인덱스) 를 저장해주면 됩니다.

길이를 같이 저장해줘야 하는데, LIS와는 달리 LCIS는 앞의 원소로 끝내는 LCIS를 더 길게 만들 수 있기 때문입니다.

그런데 그걸 신경 안 썼다가는 역추적 배열이 꼬여버리겠죠.

ll arr[520], brr[520];
int dp[520], pre[520][520];

void Main(){
	int n; cin >> n; for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	int m; cin >> m; for (int i = 1; i <= m; i++){ cin >> brr[i]; }
	memset(dp, -1, sizeof(dp)); dp[0] = 0;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			if (arr[i] != brr[j]){ continue; }
			for (int k = 0; k < j; k++){
				if (k==0 || brr[k] < brr[j]){
					if (dp[j] < dp[k]+1){
						dp[j] = dp[k]+1; pre[j][ dp[j] ] = k;
						//if (j == 4){ cout << "J4 " << dp[j] << ' ' << pre[j] << endl; }
					}
					//cout << "dp " << k << " = " << dp[k] << endl;
				}
			}
			//cout << "DP " << j << " = " << dp[j] << endl << flush;
			//system("pause");
		}
	}
	int ans = 0, ptr = 0;
	//for (int i = 1; i <= n; i++){ cout << arr[i] << ' '; } cout << endl;
	for (int i = 1; i <= m; i++){
		if (dp[i] > ans){
			ans = dp[i]; ptr = i;
		}
		//cout << "DP " << i << ' ' << brr[i] << ' ' << dp[i] << ' ' << pre[i] << endl;
	}
	cout << ans << endl; stack<ll> stk;
	while (ans--){ stk.push(brr[ptr]); ptr = pre[ptr][ans+1]; }
	while (!stk.empty()){ cout << stk.top() << ' '; stk.pop(); }
}

9. [1509] 팰린드롬 분할 (Gold I)

의도한 태그: Interval DP

우선 팰린드롬 판별을 위해 아래 DP를 만들어봅시다.

$P_{s t, e d} = S_{s t} S_{s t + 1} \dots S_{e d}$ 가 회문인지 여부

그럼 점화식은 아래 방식으로 만들어볼 수 있습니다.

$P_{s t, e d}$ 가 회문이려면, $S_{s t} = S_{e d}$ 면서 $P_{s t + 1, e d - 1}$ 여야 한다.

초항은 $P_{i, i} = True, P_{i, i + 1} = (S_{i} = S_{i + 1})$ 이 됩니다.

근데 이렇게 회문 판별을 해도, 문제는 어떻게 풀어야 할까요?

$D_{i} = S_{1} S_{2} \dots S_{i}$ 를 분할하기 위해 필요한 팰린드롬의 최소 개수

라는 DP를 하나 더 정의해보면, 아래와 같은 점화식을 생각해볼 수 있습니다.

$P_{j, i}$ 인 $j (\leq i)$ 에 대해, $D_{j - 1} + 1$ 의 최솟값

초항은 $D_{0} = 0$ 이고, 문제의 답은 $D_{N}$ 이 됩니다.

bool pal[2520][2520]; int dp[2520];

void Main(){
	string s; cin >> s; int n = s.size(); s = " " + s;
	for (int i = 1; i <= n; i++){ pal[i][i] = 1; }
	for (int i = 1; i < n; i++){ pal[i][i+1] = (s[i] == s[i+1]); }
	for (int l = 3; l <= n; l++){
		for (int i = 1; i <= n; i++){
			int j = i + l-1; if (j > n){ break; }
			pal[i][j] = (s[i] == s[j] && pal[i+1][j-1]);
		}
	}
	for (int i = 1; i <= n; i++){
		int mn = 1e9;
		for (int j = 0; j < i; j++){
			if (pal[j+1][i]){ mn = min(mn, dp[j]); }
		}
		dp[i] = mn+1;
	}
	cout << dp[n];
}

'ALOHA - 2022 > ALOHA - 초급반 → 중급반 월반 (2022 여름방학)' 카테고리의 다른 글

ALOHA 월반 5주차 - Union Find / Minimum Spanning Tree (0)	2022.08.30
ALOHA 월반 3주차 - 최단 경로 (Dijkstra / Bellman-Ford / Floyd-Warshall) (0)	2022.08.09
ALOHA 월반 2주차 - 그래프 (DFS / BFS / Backtracking) 풀이 (0)	2022.08.01
ALOHA 월반 1주차 - 완전탐색 / 그리디 / 분할정복 (0)	2022.07.27

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

인기포스트

ABOUT ME

hibye1217의 ALOHA & SHARC 탐방기 hibye1217의 ALOHA & SHARC 탐방기

1. [22971] 증가하는 부분 수열의 개수 (Silver II)

2. [2565] 전깃줄 (Gold V)

3. [25343] 최장 최장 증가 부분 수열 (Gold V)

4. [9252] LCS 2 (Gold IV)

5. [11066] 파일 합치기 (Gold III)

6. [1958] LCS 3 (Gold III)

7. [24940] Split the GSHS (Gold III)

8. [7476] 최대 공통 증가 수열 (Gold I)

9. [1509] 팰린드롬 분할 (Gold I)

'ALOHA - 2022 > ALOHA - 초급반 → 중급반 월반 (2022 여름방학)' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

인기포스트

ABOUT ME

1. [22971] 증가하는 부분 수열의 개수 (Silver II)

2. [2565] 전깃줄 (Gold V)

3. [25343] 최장 최장 증가 부분 수열 (Gold V)

4. [9252] LCS 2 (Gold IV)

5. [11066] 파일 합치기 (Gold III)

6. [1958] LCS 3 (Gold III)

7. [24940] Split the GSHS (Gold III)

8. [7476] 최대 공통 증가 수열 (Gold I)

9. [1509] 팰린드롬 분할 (Gold I)

'ALOHA - 2022 > ALOHA - 초급반 → 중급반 월반 (2022 여름방학)' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역