BOJ 20047 - 동전 옮기기

문제

문자열의 길이 n, 문자 o, x로 이루어진 문자열 S, T, 이동시킬 문자의 위치 i, j가 주어진다.
문자열 S에서 i, j 위치에 있는 문자 두 개의 위상을 유지하면서 이동시켜 T로 변환할 수 있는지 판별하는 문제이다.
이때 i, j는 [0, n)의 범위로 주어진다.

풀이

2차원 dp를 아래와 같이 설계한다. \(dp(l)(k)\) = 문자열 T의 substring [0, l]를 만들 수 있을 경우 1, 아니면 0, k의 값은 아래와 같이 정의한다.

• 0 : S에서 선택한 i, j 모두 사용한 경우
• 1 : S에서 선택한 i를 사용한 경우
• 2 : S에서 선택한 i, j를 모두 사용한 경우

S에서 i, j번째 문자를 추출하고 남은 n-2 길이의 문자열을 r이라 하면 아래 코드에서 보이는 것과 같은 점화식을 얻을 수 있다.

소스코드

#include<iostream>
#include<vector>
#include<string>

using namespace std;
using vi=vector<int>;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, a, b, f=0;
	char ca, cb;
	string s, t, r;
	cin>>n>>s>>t>>a>>b;
	ca=s[a];
	cb=s[b];
	r=s;
	r.erase(b, 1);
	r.erase(a, 1);
	vector<vi> dp(n, vi(3, -1));
	if(r[0]==t[0]) dp[0][0]=1;
	else dp[0][0]=0;
	if(ca==t[0]) dp[0][1]=1;
	else dp[0][1]=0;
	dp[0][2]=0;
	for(int i=1;i<n;i++){
		if(dp[i-1][0] && r[i]==t[i]) dp[i][0]=1;
		else dp[i][0]=0;
		if((dp[i-1][0] && ca==t[i]) || (dp[i-1][1] && r[i-1]==t[i])) dp[i][1]=1;
		else dp[i][1]=0;
		if((dp[i-1][1] && cb==t[i]) || (dp[i-1][2] && r[i-2]==t[i])) dp[i][2]=1;
		else dp[i][2]=0;
	}
	if(dp[n-1][0] || dp[n-1][1] || dp[n-1][2]) cout<<"YES";
	else cout<<"NO";
	return 0;
}

풀고나서

• 그리디로 풀게되면 아래 테스트케이스를 통과하지 못한다.

  3
  xxo
  xox
  0 2
  
  

• T의 i번째 문자가 r[i], ca 모두와 같을 때 ca를 사용하는 경우가 정답일 경우 그리디로는 답을 구할 수 없는 것이다.