[백준] 17218 비밀번호 만들기

문제

최근 들어 개인정보 유출에 대한 뉴스를 많이 본 수형이는 한 사이트의 비밀번호가 유출 되더라도 다른 사이트에서 똑같은 비밀번호로 접속할 수 없도록 사이트마다 비밀번호를 다르게 설정하기로 다짐했다. 많이 고민한 결과 수형이는 눈을 감고 키보드를 막 쳐서 나온 두 문자열에서 공통으로 존재하는 가장 긴 부분 문자열을 비밀번호로 하기로 하였다. 수형이가 눈을 감고 만든 두 문자열이 주어졌을 때 비밀번호를 만드는 프로그램을 만들어보자.

입력

첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 최대 40자이다. 빈 문자열은 주어지지 않는다. 가장 긴 부분 문자열은 반드시 하나만 존재한다.

출력

첫 번째 줄에 입력으로 주어진 두 문자열로 만든 비밀번호를 출력한다.

 

 

두 문자열의 가장 긴 공통문자열을 구하는 문제입니다.

2차원 배열의 dp를 만들어 해결할 수 있습니다.

 

이때 이렇게 구한 배열에는 각각 i,j번째 문자까지 가장 긴 문자열의 길이를 저장합니다.

따라서 이 배열을 이용해 문자열을 구할때는, 맨 끝에서부터 따라가면서 구하면 됩니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;
string A, B;
int dp[41][41];
int main() {
	FAST;
	cin >> A >> B;
	for (int i = 0; i < B.size(); i++) {
		for (int j = 0; j < A.size(); j++) {
			if (B[i] == A[j]) {
				dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j]+1);
			}
			else {
				dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
			}
		}
	}
	vector<char>st;
	int j = B.size(), i = A.size();
	while (1) {
		while (dp[j][i] == dp[j][i - 1] && i>0) {
			i--;
			
		}
		while (dp[j][i] == dp[j - 1][i] && j > 0) {
			j--;
		}
		if (!j || !i)break;
		st.push_back(B[j - 1]);
		j--;
	}
	while (!st.empty()) {
		cout << st.back();
		st.pop_back();
	}
}