[BOJ] 17218 - 비밀번호 만들기

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

아이디어

각 주어진 문자열을 1번 문자열, 2번 문자열로 칭하자.
사용 가능한 최대 비밀번호를 알기 위해서는 완전탐색을 하는 것이 가장 간단한 아이디어일 것이다.
1번 문자열을 기준으로 해당 문자를 비밀번호에 사용하는 경우와, 사용하지 않는 경우 두 가지로 나누어 비밀번호로 사용할 수 있을 경우만 현재 문자열을 저장해준다.
따라서 모든 경우에 대해 최대 문자열을 탐색할 수 있다.
그러나 이 경우 당연히 시간복잡도를 초과하게 된다.
따라서 DP를 적용해 중복되는 계산 과정을 줄여 시간복잡도를 줄여주었다.

구현

DP[현재 확인하고 있는 1번 문자열의 위치][현재 상태에서 마지막으로 찾은 2번 문자열의 위치]
이렇게 써주었다!
처음에는 1번 문자열의 위치만 고려해주었는데, 그럴 경우 2번 문자열이 해당 위치에서 더 앞부터 탐색할 수 있는 경우가 있음에도 더 뒤에서 탐색하는 경우를 먼저 탐색하면 최적의 경우를 DP값에 저장하지 못하는 문제가 있었다.(말이 이상한데 설명이 잘 되었을지 모르겠다.)
나머지는 bottom-up방식으로 재귀를 이용해 해결했다.

소스코드

#include <iostream>
#include <string.h>
#include <string>

using namespace std;

bool check[45];
char str1[45], str2[45];
string dp[45][45], ans;

string go(int now, int lp) {
	if (now >= strlen(str1))
		return "";
	if (dp[now][lp] != "") {
		return dp[now][lp];
	}
	string rtn = "";
	for (int i = lp; i < strlen(str2); i++) {
		if (check[i]) continue;
		if (str1[now] == str2[i]) {
			check[i] = true;
			rtn += str2[i];
			rtn += go(now + 1, i + 1);
			check[i] = false;
			break;
		}
	}
	string rtn2 = go(now + 1, lp);
	dp[now][lp] = rtn.length() > rtn2.length() ? rtn : rtn2;
	if (dp[now][lp].length() > ans.length()) ans = dp[now][lp];
	return dp[now][lp];
}

int main(void) {
	cin >> str1;
	cin >> str2;
	go(0, 0);
	cout << ans;
	return 0;
}