월반멘토링 4주차 set 풀이
13 Aug 2022방학이 끝나간..드아..
어째 풀이가 불친절해지는거 같으면 기분탓이 아니에요 더위 먹어서 힘들어..
DP(Interval DP) / LIS / LCS
1. 증가하는 부분 수열의 개수 (Silver II)
tag : lis(\(\scriptsize O(N^{2})\))
\(\scriptsize i\)번째 원소로 끝나는 LIS의 개수를 세는 문제다.
\(\small dp(i) := "i\)번째 원소로 끝나는 LIS 개수”
라고 정의하면 된다. 그러면, 당연하게도 다음과 같은 점화식을 얻는다.
\[\small dp(i) = \sum_{j < i \wedge arr(j) < arr(i)}dp(j)\]
이 점화식은 \(\scriptsize O(N^{2})\)에 계산할 수 있으므로, 시간내에 결과를 다 구할 수 있다. 따라서, DP 테이블을 채우고 출력하면 AC.
코드 보기
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;
ll A[5050];
ll dp[5050];
const ll MOD = 998244353LL;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N; cin >> N;
for(int i = 1; i <= N; ++i) cin >> A[i];
for(int i = 1; i <= N; ++i) {
dp[i] = 1;
for(int j = 1; j < i; ++j) {
if(A[j] < A[i]) {
dp[i] += dp[j];
dp[i] %= MOD;
}
}
}
for(int i = 1; i <= N; ++i) cout << dp[i] % MOD << ' ';
return 0;
}
2. 전깃줄 (Gold V)
tag : lis
교차하지 않으려면 \(\scriptsize A\)전봇대의 낮은 번호에서부터 볼 때, \(\scriptsize B\)에 연결되어 있는 번호들이 증가하는 모습을 보여야 한다. 연결된 번호가 감소한다면 교차한다는 의미이다.
문제에서 구하는 것은 교차하지 않도록 하기 위해 없애야 하는 최소 전선의 개수이다. 반대로 생각해보자. 가장 긴 증가하는 부분 수열의 길이가 바로 교차하지 않으며 존재할 수 있는 최대 전선의 개수이다. 즉 LIS의 길이를 찾고 (전체 전선 개수 - LIS 길이)을 해주면 정답이다.
이때, \(\scriptsize N\)의 크기가 100으로 작기 때문에, \(\scriptsize O(N^{2})\)짜리 시간복잡도로 LIS 길이를 구해도 된다. 전봇대 \(\scriptsize A\)에 연결된 \(\scriptsize B\) 위치를 차례대로 넣어두고, LIS를 찾으면 된다.
코드 보기
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int N; cin >> N;
vector<int> dp(N, 1);
vector<pair<int, int>> seq(N);
for(int i = 0; i < N; ++i) cin >> seq[i].first >> seq[i].second;
sort(seq.begin(), seq.end());
for(int i = 0; i < N; ++i) {
for(int j = 0; j < i; ++j) {
if(seq[i].second > seq[j].second) {
dp[i] = max(dp[i], 1 + dp[j]);
}
}
}
int lis = *max_element(dp.begin(), dp.end());
cout << N - lis << '\n';
return 0;
}
3. 최장 최장 증가 부분 수열 (Gold V)
tag : lis
문제를 잘 읽어보면, 2차원에서 LIS를 구하는 문제라 생각할 수 있다. 이때, 최단경로로 이동하므로 오른쪽과 아래쪽으로만 움직일 수 있다.
1차원에서 LIS를 구할 때 정의했던 식과 비슷하게 dp식을 정의해보자.
\(\small dp(i, j) := "(i, j)\)까지 만들 수 있는 최장 증가 부분 수열의 길이”
\[\small dp(i, j) = \max_{arr(r, c) < arr(i, j)}dp(r, c) + 1\]단, \(\small r \leq i \wedge c \leq j \wedge (r, c) \neq (i, j)\)
따라서, DP 테이블은 \(\scriptsize O(N^{4})\)에 구할 수 있다. \(\scriptsize N = 100\)이라서, 충분히 구할 수 있다.
여담으로, 원래 출제자는 이걸 이차원 세그먼트 트리로 최적화 하는.. 문제로 내려 했었답니다. 그걸로 풀면 \(\scriptsize O(N^{2}log^{2}N)\)에 풀림.
코드 보기
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;
int dp[101][101];
int m[101][101];
int N;
int solve(int i, int j) {
int& ret = dp[i][j];
if(ret != -1) return ret;
ret = 1;
for(int r = 1; r <= i; ++r) {
for(int c = 1; c <= j; ++c) {
if(r == i && c == j) continue;
if(m[r][c] < m[i][j]) ret = max(ret, solve(r, c) + 1);
}
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
for(int i = 1; i <= N; ++i) {
fill(dp[i], dp[i] + 101, -1);
for(int j = 1; j <= N; ++j) {
cin >> m[i][j];
}
}
int ans = 0;
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= N; ++j) {
ans = max(ans, solve(i, j));
}
}
cout << ans << '\n';
return 0;
}
4. LCS2 (Gold IV)
tag : LCS
LCS를 구하고, LCS 중 하나를 출력하면 된다. 간단히 말하면 LCS를 역추적하는 문제다.
void traceLCS(string& str, int a, int b) {
vector<char> ret;
while(a >= 0 && b >= 0) {
if(dp[a][b] == dp[a - 1][b]) a--;
else if(dp[a][b] == dp[a][b - 1]) b--;
else {
ret.push_back(str[a]);
a--; b--;
}
}
}
dp[a][b] == dp[a - 1][b]이면, 왼쪽을 감소시키면 된다. 반대로 dp[a][b] == dp[a][b - 1]이면, 오른쪽을 감소시키자. 저 두 경우가 아니면 dp값에 변화가 있어야 했던 부분이니까 둘 다 감소시켜주자. 이런식으로 LCS의 실제값을 구해낼 수 있다. 이해가 안된다면, 직접 dp값을 써보면서 이해하는걸 추천함.
코드 보기
// https://www.acmicpc.net/problem/9251 //
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int dp[1001][1001];
int LCS(string& str1, string& str2, int idx1, int idx2) {
if(idx1 < 0 || idx2 < 0) return 0;
int& res = dp[idx1][idx2];
if(res != -1) return res;
if(str1[idx1] == str2[idx2]) return res = LCS(str1, str2, idx1 - 1, idx2 - 1) + 1;
else return res = max(LCS(str1, str2, idx1 - 1, idx2), LCS(str1, str2, idx1, idx2 - 1));
}
void traceLCS(string& str, int a, int b) {
vector<char> ret;
while(a >= 0 && b >= 0) {
if(dp[a][b] == dp[a - 1][b]) a--;
else if(dp[a][b] == dp[a][b - 1]) b--;
else {
ret.push_back(str[a]);
a--; b--;
}
}
for(int i = ret.size() - 1; i >= 0; --i) cout << ret[i];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
string str1, str2;
cin >> str1 >> str2;
for(int i = 0; i < 1001; ++i) {
fill_n(dp[i], 1001, -1);
}
cout << LCS(str1, str2, str1.size() - 1, str2.size() -1) << '\n';
traceLCS(str1, str1.size() - 1, str2.size() - 1);
return 0;
}
5. 파일 합치기 (Gold III)
tag : dp(interval dp), prefix-sum
구간을 dp 정의식에 포함해야하는 dp이다. 이거 처음 배울 때 엄청 어려웠던 기억이.. 다음과 같은 dp 정의식을 떠올려보자.
\(\small dp(i, j) := "[i, j]\)번째 파일을 합치는 데 드는 최소 비용”
라고 하면, 점화식을 하나 생각할 수 있다.
\[\small dp(i, j) = \min_{i \leq k < j} dp(i, k) + dp(k + 1, j) + \sum_{a = i}^{j} cost(a)\]
즉, 중간 지점에서 나누어서 합치는 걸로 점화식을 세울 수 있다. \(\scriptsize [i, j]\) 구간의 파일을 합치는 비용의 최솟값은 합쳐진 \(\scriptsize [i, k]\) 파일과 합쳐진 \(\scriptsize [k + 1, j]\) 파일을 합치는 비용의 최소와 같다.
이때, 두 파일을 합치는데 드는 비용은 고정적이다. 따라서, 해당 파트는 prefix-sum 으로 처리할 수 있다. prefix-sum은 간단히 설명하자면, 구간합을 \(\scriptsize O(1)\)에 구할 수 있도록 하는 기법이고 앞에서부터 누적합을 저장한 뒤 적절히 빼는 방식으로 사용할 수 있다. 자세한 설명은 다른 분들이 자세하게 해놨으니 따로 찾아서 공부하는걸 추천드립니다.
하여튼, 저 점화식에 의하면 테이블을 채우는데, \(\scriptsize O(N^{3})\)이니 잘 계산해주면 맞출 수 있다.
(진짜 TMI로 Knuth Optimization(크누스 최적화)라는 것도 적용할 수 있는데.. 이걸 할 줄 알면 이 문제가 \(\scriptsize O(N^{2})\)에 풀리고, 그 문제는 심지어 플래티넘2짜리 문제다. 관심있으면 찾아보세요.)
코드 보기
#include <iostream>
#include <vector>
#define INF 987654321
using namespace std;
void solve(vector<int>& seq, int K) {
vector<vector<int>> dp(K, vector<int>(K, 0));
vector<int> sum(K + 1, 0);
for(int i = 1; i <= K; ++i) sum[i] = sum[i - 1] + seq[i - 1];
for(int length = 1; length < K; ++length) {
for(int start = 0; start <= K - length - 1; ++start) {
int end = start + length;
dp[start][end] = INF;
for(int pivot = start; pivot + 1 <= end; ++pivot) {
int cost = dp[start][pivot] + dp[pivot + 1][end] + sum[end + 1] - sum[start];
dp[start][end] = min(cost, dp[start][end]);
}
}
}
cout << dp[0][K - 1] << '\n';
}
int main() {
int T; cin >> T;
while(T --> 0) {
int K; cin >> K;
vector<int> seq(K);
for(int i = 0; i < K; ++i) cin >> seq[i];
solve(seq, K);
}
return 0;
}
6. LCS3 (Gold III)
tag : LCS
아마 스트링 2개짜리 LCS 점화식을 혼자서 구할 수 있으면 진짜 쉽게 풀 수 있는 문제다. 그냥 단지 스트링이 2개에서 3개로 늘어난거기 때문에 점화식도 그에 맞춰서 확장시키면 된다.
정확히 2개짜리 LCS와 유사하게 점화식을 세우고, str1[i] == str2[i] == str3[i]일때 범위를 모두 하나씩 줄여가며 LCS를 찾으면 된다. 위의 경우가 아닐때도 그냥 2개짜리 LCS와 비슷하게 해서 max값을 구하면 됨.
다만, 3개로 늘어났기에 시간복잡도는 \(\scriptsize O(N^{3})\)이 된다.
자세한 건 코드를 참고!
코드 보기
// https://www.acmicpc.net/problem/1958 //
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[101][101][101];
int LCS(string& str1, string& str2, string& str3, int idx1, int idx2, int idx3) {
if(idx1 < 0 || idx2 < 0 || idx3 < 0) return 0;
int& res = dp[idx1][idx2][idx3];
if(res != -1) return res;
if(str1[idx1] == str2[idx2] && str2[idx2] == str3[idx3]) return res = LCS(str1, str2, str3, idx1 - 1, idx2 - 1, idx3 - 1) + 1;
else return res = max({LCS(str1, str2, str3, idx1 - 1, idx2, idx3), LCS(str1, str2, str3, idx1, idx2 - 1, idx3), LCS(str1, str2, str3, idx1, idx2, idx3 - 1)});
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
string str1, str2, str3;
cin >> str1 >> str2 >> str3;
for(int i = 0; i < 101; ++i) {
for(int j = 0; j < 101; ++j) {
fill_n(dp[i][j], 101, -1);
}
}
cout << LCS(str1, str2, str3, str1.size() - 1, str2.size() -1, str3.size() - 1);
return 0;
}
7. Split the GSHS (Gold III)
tag : dp(interval-dp)
풀고 나중에 업데이트 할게요.
edit : 2022-08-17 02:11 풀이 업데이트
파일합치기와 비슷한 냄새가 난다.
\(\small dp(i, j) := "[i, j]\)를 합칠 때 최소 친밀도 값”
이라고 정의하면, 쉽게 관계식을 찾을 수 있다.
\[\small dp(l, r) = \min_{l\leq k < r}{(dp(l, k) + dp(k + 1, r) -\mid xy\mid)}\](단, \(\small \mid xy\mid\)는 \(\small x, y\)의 부호가 서로 다를때만 있는 값이다. 부호가 같거나 0일때는 0의 값을 가짐.)
즉, 구간별로 합칠 때 최소값을 찾아서 전체 문제의 최소값을 찾을 수 있다.
이때, \(\scriptsize x, y\)는 prefix-sum으로 \(\scriptsize O(1)\)에 찾을 수 있으므로 총 시간복잡도 \(\scriptsize O(N^{3})\)에 해결 가능하다.
코드 보기
// 아직 없지롱 우헤헤
//*edit : 2022-08-17 02:11 풀이 업데이트*
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;
const ll INF = 1e18;
ll A[81];
ll dp[81][81];
ll pf_sum[81];
int N;
void init() {
for(int i = 0; i < 81; ++i)
fill(dp[i], dp[i] + 81, -INF);
for(int i = 1; i <= N; ++i)
pf_sum[i] = pf_sum[i - 1] + A[i];
}
ll get_min(int l, int r) {
ll& ret = dp[l][r];
if(ret != -INF) return ret;
if(l == r) return ret = 0;
ret = 0;
for(int k = l; k < r; ++k) {
ll x = pf_sum[k] - pf_sum[l - 1];
ll y = pf_sum[r] - pf_sum[k];
if(x < 0 && y > 0 || x > 0 && y < 0)
ret = min(ret, x * y + get_min(l, k) + get_min(k + 1, r));
else
ret = min(ret, get_min(l, k) + get_min(k + 1, r));
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
for(int i = 1; i <= N; ++i)
cin >> A[i];
init();
cout << get_min(1, N) << '\n';
return 0;
}
8. 최대 공통 증가 수열 (Gold I)
tag : dp(interval-dp)
풀고 나중에 업데이트 할게요.
//edit : 2022-08-20 15:50 풀이 업데이트
이왜골?
\(\scriptsize O(N^{4})\) 풀이는 아마 떠올릴 수 있을거라 생각합니다.
당연히, \(\scriptsize O(N^{4})\) 풀이는 Naive하게 짜서 그대로 제출하면 시간초과를 받는다.
\(\small dp(i, j) := "A_{i}, B_{j}\) 부터 시작하는 최대 공통 증가 수열 길이” (단, \(\small A_{i} = B_{j}\))
\[\small dp(i, j) := \max_{x > i \wedge y > j} (dp(x, y) + 1)\]
즉, \(\scriptsize O(N^{2})\)개의 부분문제를 계산하는데, \(\scriptsize O(N^{2})\)번 계산을 해야해서 \(\scriptsize O(N^{4})\)이다.
이대로 제출하면, 2%에서 시간초과를 받고 뻗는다.
음.. 그럼 \(\scriptsize N\)을 하나 떼던가 해야 AC를 받을 수 있을거란 생각을 하게 된다. 같은 학술부 hibye1217님은 정직한 \(\scriptsize O(N^{3})\)에 해결했다. 근데, 난 그 방법은 생각하지 못했고, \(\scriptsize O(N^{4})\) 풀이에서 최적화를 통해 문제를 해결했다.
즉, 이제부터 설명할 풀이는 최악의 시간복잡도가 \(\scriptsize O(N^{4})\)이 맞는데, 가지가 많이 쳐내져서 AC를 받을 수 있는..(?) 최적화 풀이이다. \(\scriptsize O(N^{3})\) 풀이가 궁금한 분들은 hibye1217님의 블로그를 참고합시다.
먼저, 모든 \(\scriptsize (x, y)\) 쌍에 대해 값을 가져올 필요가 없다. \(\scriptsize A\)를 기준으로 생각하면, 현재 값보다 큰 값들 중 하나를 골랐을 때, \(\scriptsize B\)에서는 가장 먼저 등장하는 값의 최대 공통 증가 수열 길이를 들고오면 된다.
같은 값이 여러개가 있으면, 가장 앞에서 시작해야 길이가 더 길 것이라 그렇다. 이 정도의 최적화를 해주면 \(\scriptsize O(N^{4})\)이지만, 시간 내에 놀랍게도 돌아간다.
이제 최대 공통 증가 수열을 트래킹해서 같이 출력해주면, 정답을 받을 수 있다. 트래킹하는 방법은 여러가지가 있겠지만 std::map을 사용하면, 어렵지 않게 할 수 있다. 현재 \(\scriptsize (x, y)\) 쌍의 다음 쌍을 저장해놓고 다음 쌍이 없을 떄까지 출력해주면 된다.
자세한건 코드를 참고하세요~
코드 보기
// 아직 없어 우히히
//*edit : 2022-08-20 15:50 풀이 업데이트*
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;
int dp[501][501];
int A[501];
int B[501];
map<pair<int, int>, pair<int, int>> next_value;
int N, M;
void init() {
for(int i = 0; i < 501; ++i)
fill(dp[i], dp[i] + 501, -1);
}
int solve(int x, int y) {
int& ret = dp[x][y];
if(ret != -1) return ret;
ret = 1;
next_value[{x, y}] = {-1, -1};
for(int i = x + 1; i <= N; ++i) {
if(A[x] >= A[i]) continue;
for(int j = y + 1; j <= M; ++j) {
if(A[i] == B[j]) {
if(ret < solve(i, j) + 1) {
ret = solve(i, j) + 1;
next_value[{x, y}] = {i, j};
}
break;
}
}
}
return ret;
}
void tracking(int a, int b) {
if(a <= 0 || b <= 0) return;
cout << A[a] << ' ';
tracking(next_value[{a, b}].first, next_value[{a, b}].second);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
for(int i = 1; i <= N; ++i) cin >> A[i];
cin >> M;
for(int i = 1; i <= M; ++i) cin >> B[i];
init();
int ans = 0;
int a = -1, b = -1;
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= M; ++j) {
if(A[i] == B[j]) {
if(ans < solve(i, j)) {
ans = solve(i, j);
a = i;
b = j;
}
break;
}
}
}
cout << ans << '\n';
tracking(a, b);
return 0;
}
9. 팰린드롬 분할 (Gold I)
tag : dp
7, 8 해설과 함께 올라올 예정. 코드는 미리 첨부해놨음!
//edit : 2022-08-20 15:50 풀이 업데이트
갑자기 이런 dp식을 떠올려보자.
\(\small dp(n) := "[0, n]\) 구간에서 최소 팰린드롬 분할 개수”
\[\small dp(n) = \min_{0 \leq k \leq n \wedge \text{[k, n] is pldr}} dp(k - 1) + 1\]
즉, \(\scriptsize [0, n] = [0, k - 1] + [k, n]\) 으로 생각하면, 앞 구간과 뒷 구간으로 나눠 생각할 수 있는데, 뒷 구간이 팰린드롬인지 검사하고 앞에서 최소 개수를 얻어오는 것이다. 이때, \(\scriptsize k = 0\)이면 앞 구간 팰린드롬 분할 수가 0인걸로 생각하면 된다.
팰린드롬 전처리는 \(\scriptsize O(N^{2})\)에 할 수 있다. \(\scriptsize N = 2500\)이므로, 시간 내에 전처리 할 수 있다. (스트링 길이 생각안하고, 나이브하게 짜도 시간 내에 돌아감.)
이 점화식을 그대로 짜면 맞출 수 있다. 아마 dp식을 2차원으로만 생각하고 있었다면, 꽤 헤맬 수 있는 문제였다.
코드 보기
#include <iostream>
#include <vector>
#include <string>
#define MAX 2500
using namespace std;
int dp[MAX];
bool isPldr[MAX][MAX];
string str;
void isPalindrome(string& str, int a, int b) {
for(int i = 0; i <= (b - a) / 2; ++i) {
if(str[a + i] != str[b - i]) {
isPldr[a][b] = false;
return;
}
}
isPldr[a][b] = true;
}
int solve(string& str, int n) {
if(n < 0) return 0;
int& ret = dp[n];
if(ret != -1) return ret;
ret = MAX + 1;
for(int k = 0; k <= n; ++k) {
if(isPldr[k][n]) ret = min(ret, 1 + solve(str, k - 1));
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
for(int i = 0; i < MAX; ++i) dp[i] = -1; //init
cin >> str;
for(int i = 0; i < (int)str.size(); ++i) {
for(int j = i; j < (int)str.size(); ++j) {
isPalindrome(str, i, j);
}
}
cout << solve(str, (int)str.size() - 1);
return 0;
}