백준[20046] 동전 옮기기

아이디어

• DP를 사용할 줄 안다

접근방식

1. 기본 입력을 받고, S 문자열에서 옮길 동전을 따로 저장, S에서 옮길 동전을 뺀 문자열을 따로 저장해준다
2. DFS를 돌면서 t 문자열의 0번부터 끝번까지 조사를 한다.
   1. 새로운 S 위치의 문자와 t 위치의 문자가 같으면 두 위치를 1씩 증가시키고 dfs를 시행한다.
   2. 만약 cnt == 0 (따로 뺀 동전을 사용 안함) 이고 첫번째 뺀 동전을 사용할 경우 cnt +1 을 해준 후 함수를 실행한다(순서를 지켜야 하기에 cnt==0일때는 무조건 첫번째 동전만 사용할 수 있다)
   3. 만약 cnt == 1일 경우(첫번째 동전 이미 사용) 이고 두번째 뺀 동전을 사용할 경우, (2)번 경우와 비슷하게 cnt + 1 을 해준다. (첫번째 동전이 언제 사용되는지는 알필요 없다. 사용했냐 안했냐만 중요하다)
   4. 만약 tpos == t.size() && cnt == 2 일 경우 t의 모든 문자를 조사할 수 있고, 동전 2개를 사용했다는 뜻이므로, answer == true로 바꾸고 종료해준다.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <string>
#include <math.h>
#include <queue>
using namespace std;

bool answer = false;

void dfs(string& s, string& t, char first, char sec, int spos, int tpos, int cnt) {
	if (tpos == t.size() && cnt == 2) {
		answer = true;
		return;
	}
	if (spos < s.size()) {
		if (s[spos] == t[tpos]) dfs(s, t, first, sec, spos + 1, tpos + 1, cnt);
	}

	if (cnt == 0) {
		//첫번째껄 넣을 수 있으면
		if (t[tpos] == first) {
			dfs(s, t, first, sec, spos, tpos + 1, cnt + 1);
		}
	}
	if (cnt == 1) {
		//두번쨰꺼
		if (t[tpos] == sec) {
			dfs(s, t, first, sec, spos, tpos + 1, cnt + 1);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n; cin >> n;
	string s, t; cin >> s >> t;
	int i, j; cin >> i >> j;

	char first = s[i];
	char sec = s[j];

	string new_s;
	for (int k = 0; k < s.size(); k++) {
		if (k != i && k != j) new_s.push_back(s[k]);
	}

	dfs(new_s, t, first, sec, 0, 0, 0);

	if (answer == false) {
		cout << "NO" << endl;
	}

	else {
		cout << "YES" << endl;
	}

	return 0;
}

평가

DP? 라고 해야할 지, 구현을 해주면 쉽게 풀 수 있는 문제.
.. 이지만 필자는 처음 이 문제를 접했을때 못풀었습니다.
ICPC 대비 겸 PS를 하고 있었는데 그리디 인줄알고 처음부터 비교하다가, 반례를 발견해서 당황한 나머지, DP나 DFS가 생각이 나지 않아 결국 못풀었습니다.
그러다, 다음 날 보니 10분만에 풀이 방법이 떠올라 바로 맞힐 수 있었습니다.
개인적으로 충분히 풀 수 있는데 못풀어서 굉장히 아쉬운 문제였습니다.