https://www.acmicpc.net/problem/17218
17218번: 비밀번호 만들기
첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 최대 40자이다. 빈 문자열은 주어지지 않는다. 가장 긴 부분 문자열
www.acmicpc.net
[난이도] Gold5
[유형] DP
[풀이]
전형적인 LCS (DP) 문제입니다.
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
string A,B;
int dp[41][41];
pair<int,int> par[41][41];
int main(){
cin >> A >> B;
for(int i=0;i<A.size();i++){
for(int j=0;j<B.size();j++){
if(A[i]==B[j]) {
dp[i+1][j+1] = dp[i][j]+1;
par[i+1][j+1] = {i,j};
}else{
if(dp[i+1][j] > dp[i][j+1]){
dp[i+1][j+1] = dp[i+1][j];
par[i+1][j+1] = {i+1,j};
}else{
dp[i+1][j+1] = dp[i][j+1];
par[i+1][j+1] = {i,j+1};
}
}
}
}
string ans;
int i=A.size(),j=B.size();
while(i!=0&&j!=0){
if(A[i-1] == B[j-1]) ans+=A[i-1];
auto v = par[i][j];
i=v.first;
j=v.second;
}
reverse(ans.begin(),ans.end());
cout << ans;
}
https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/17218.cpp
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold5] 18428 : 감시 피하기 (C++) (0) | 2022.11.06 |
|---|---|
| [BOJ/백준][Gold5] 15661 : 링크와 스타트 (C++) (0) | 2022.11.06 |
| [BOJ/백준][Gold4] 2253 : 점프 (C++) (0) | 2022.11.06 |
| [BOJ/백준][Silver3] 16967 : 배열 복원하기 (C++) (0) | 2022.11.06 |
| [BOJ/백준][Silver2] 2210 : 숫자판 점프 (C++) (0) | 2022.11.06 |