백준 20047번 동전 옮기기

🔒[문제 url]

https://www.acmicpc.net/problem/20047

🔑알고리즘

$S$에서 선택한 두 동전을 제외한 순서에서, 두 동전을 재배치함으로써 $T$를 만들어야한다.
$S$에서 두 동전을 제외한 순서를 $K$라고 하자.

• $K$와 $T$의 배치를 앞에서부터 비교해가며 배치할 동전을 결정한다.
  배치할 방법은 다음과같이 2가지이므로, DFS를 진행한다.

1. 현재 $K$의 동전과 현재 $T$의 동전이 같을 경우, $K$의 동전을 배치한다.
2. 현재 $K$의 동전과 현재 $T$의 동전이 같을 경우, $S$에서 제외했던 동전을 배치한다. 이때, 제외한 동전은 2개임에 주의하여 배치한다.

🐾부분 코드

bool DFS(int idx,int tIdx,int cnt)
{//K의 idx , T의 idx , 배치한 동전의 수
	bool rtn = false;
    
    //끝까지 배치했다면 true 반환
	if(tIdx == n) return rtn = true;

    //제외한 동전 중 하나를 순서에 맞게 배치
	if(cnt != 2 && coin[cnt] == T[tIdx])
        //제외한 동전의 수는 2개이므로 cnt != 2여야한다.
		rtn = max(rtn,DFS(idx,tIdx+1,cnt+1));
    //현재 K의 동전를 배치
	if(K[idx] == T[tIdx])
		rtn = max(rtn,DFS(idx+1,tIdx+1,cnt));

	return rtn;
}

<DFS 함수>
위에서 설명한 2가지 배치 방법에 따라 DFS를 진행한다.
제외한 동전을 배치할 때, 이미 제외된 동전을 배치한 갯수와 배치 순서에 유의한다.

void SOLVE()
{
	coin[0] = S[l]; coin[1] = S[r];
	for(int i = 0; i < n; i++)
		if(i != l && i != r)
			K += S[i];

	if(DFS(0,0,0)) cout << "YES";
	else cout << "NO";

}

<제외한 동전과 K 초기화>
DFS를 위해 $S$에서 옮길 두 동전을 제외한 배치 $K$를 초기화한다.

🪄전체 코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int n;
string S,T;
int l,r;

char coin[2];//제외한 동전
string K = "";//S에서 선택한 동전을 제외한 후의 동전 배치

void INPUT()
{
	IAMFAST
	cin >> n >> S >> T >> l >> r;
}

bool DFS(int idx,int tIdx,int cnt)
{//K의 idx , T의 idx , 배치한 동전의 수
	bool rtn = false;
    
    //끝까지 배치했다면 true 반환
	if(tIdx == n) return rtn = true;

    //제외한 동전 중 하나를 순서에 맞게 배치
	if(cnt != 2 && coin[cnt] == T[tIdx])
        //제외한 동전의 수는 2개이므로 cnt != 2여야한다.
		rtn = max(rtn,DFS(idx,tIdx+1,cnt+1));
    //현재 K의 동전를 배치
	if(K[idx] == T[tIdx])
		rtn = max(rtn,DFS(idx+1,tIdx+1,cnt));

	return rtn;
}

void SOLVE()
{
	coin[0] = S[l]; coin[1] = S[r];
	for(int i = 0; i < n; i++)
		if(i != l && i != r)
			K += S[i];

	if(DFS(0,0,0)) cout << "YES";
	else cout << "NO";

}

int main()
{
	INPUT();
	SOLVE();
}

🥇문제 후기

흠... 문제를 보자마자 DFS 코드를 작성하고 One try AC를 받은 케이스라,
태그를 열어보니 DP라서 조금 놀랐다.
이미 배치한 동전은 유지된 채 계속 진행돼서 그런건가..?!
다만, 확실히 빠르게 DFS 풀이를 떠올리는게 쉽지는 않은 것같다.