반응형
728x170
어려웠다.
부분으로 쪼갤 수 있었지만 생각이 잘 안났다.
https://www.acmicpc.net/problem/9251
모든 부분을 부분수열로 쪼개보니.. for문이 3개나 나와서 그냥 떄려쳤다.
DP문제라는 것을 한 번에 파악할 수 있었다.
어떻게 전체 문제를 부분으로 쪼갤 수 있을까 고민했다.
처음에는 맨앞에서부터 접근했지만 틀린 접근법이었다.
마지막부터 조사했어야 했다.
길이가 L1, L2의 문자열이 있다.
만약 마지막 부분이 같다면
해당 마지막부분을 제외한 채로 나머지 L1 -1 , L2 - 1의 문자열의 가장 긴부분을 조사하면 될 터였다.
마지막 부분이 다르다면
둘 다 제외하는 것이 아닌
L1 - 1, L2 또는 L1, L2 - 1의 문자열을 조사하면되었다.
그리고 문자열이 비어있는 것과의 LCS값은 항상 0이 나와야만 했다.
이렇게 나눈 것을 코딩하기가 조금 힘들었다.
한 번 보자
#include <iostream>
#include <string>
using namespace std;
//문자열
string s1,s2;
int l1,l2;
//LCS(a,b) 의 값을 저장하기 위한 dp table
//LCS (x,y) = LCS(x',y') ... 으로 쪼개서 풀기 위함
int dp[1002][1002];
void init(){
cin.tie(0);
ios::sync_with_stdio(0);
}
int max(int a, int b){
return a > b ? a : b;
}
int main(){
init();
getline(cin,s1);
getline(cin,s2);
l1 = s1.length();
l2 = s2.length();
//등호가 붙은 것은 부분집합 중 공집합도 포함시키기 위함이다.
for(int i = 0; i<=l1; i++){
for(int j = 0; j<=l2; j++){
//공집합과의 부분비교는 항상 0의 길이가 나온다.
if(i == 0 || j == 0){
dp[i][j] = 0;
continue;
}
//다르다면 둘 중 어느 한쪽의 문자열을 제외하고 비교한다.
if(s1[i-1] != s2[j-1]){
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}else{
//같다면 둘다 제외하고 나머지 문자열의 LCS를 구한다.
dp[i][j] = dp[i-1][j-1]+1;
}
}
}
cout << dp[l1][l2];
}
항상 여기서의 핵심은
문제를 쪼갤 수 있느냐이다.
그리고 어떻게 쪼개느냐이다.
문자열의 끝만 비교해서 점차 작은 문제로 나눈다는 생각을 하기가 제일 어려웠다.
이 문제에서 가장 시간이 오래걸리는 부분이었다.
시간의 90%정도를 문자열 끝을 비교하는 것을 생각하는 데에 썼다.
728x90
반응형
그리드형
'문제풀이(Problem Solving)' 카테고리의 다른 글
백준, BOJ, 1520번, 내리막 길 : C++ [CPP] (0) | 2021.09.25 |
---|---|
백준, BOJ, 2225번, 합분해: C++ [CPP] (0) | 2021.09.13 |
백준, BOJ, 2293번 C++ [CPP] * (0) | 2021.09.01 |
백준, BOJ, 2193번 C++ [CPP] (0) | 2021.08.31 |
백준, BOJ, 17298번 C++ [CPP] (0) | 2021.08.28 |