[BOJ 20047] 동전 옮기기

백준 20047

www.acmicpc.net/problem/20047

20047번: 동전 옮기기

손가락으로 짚은 두 동전을 편의상 Fcoin이라고 하자.

 

 

1. 문자열 S(Fcoin을 제외), T의 인덱스를 증가시키면서 비교하고, 달라지는 경우에 T와 Fcoin을 비교했다.

 

   그럴 경우 반례가 생긴다.

-> 문자열 S(Fcoin을 제외)에서 비교할 문자와 와 Fcoin이 같은 경우 어떤 경우로 체크해줘야 하는지 고려하지 않았다.

 

3
xxo
xox
0 2
ans : YES

 

 

2. dp로 풀 수 있다는 사실을 알고 다시 풀었다.

 

   dp[문자열의 인덱스][사용한 Fcoin의 개수]

 

점화식

dp[n][0] =  dp[n-1][0] && S,T비교

dp[n][1] = (dp[n-1][0] && T,Fcoin1비교) || (dp[n-1][1] && S,T비교)

dp[n][2] = (dp[n-1][1] && T,Fcoin2비교) || (dp[n-1][2] && S,T비교)

 

// dp[n-2][0], dp[n-1][0], dp[n-1][1]은 항상 0이기 때문에, 비교할 때 out of range를 피하기 위해 임의로 뒤에 두 공간을 채웠다.

#include <iostream>
#include <vector>
using namespace std;
vector<char> s, t;
bool dp[10001][3] = { false, };
char str[2];
int n;

int main() {
	cin >> n;

	for (int i = 0;i < n;i++) {
		char k;
		cin >> k;
		s.push_back(k);
	}
	for (int i = 0;i < n;i++) {
		char k;
		cin >> k;
		t.push_back(k);
	}
	int x, y;
	cin >> x >> y;

	str[0] = s[x]; str[1] = s[y];
	s.erase(s.begin() + x); s.erase(s.begin() + y - 1);
	s.push_back('n'); s.push_back('n'); //임의로 뒤에 채우기
	
	//초기화
	if (s[0] == t[0])
		dp[0][0] = true;
	if (t[0] == str[0])
		dp[0][1] = true;
        
	//점화식
	for (int i = 1;i < n;i++) {
		dp[i][0] = dp[i - 1][0] && (s[i] == t[i]);
		dp[i][1] = (dp[i - 1][0] && (str[0] == t[i])) || (dp[i - 1][1] && (s[i - 1] == t[i]));
		dp[i][2] = (dp[i - 1][1] && (str[1] == t[i])) || (dp[i - 1][2] && (s[i - 2] == t[i]));
	}

	//출력
	if (dp[n - 1][2])
		cout << "YES\n";
	else cout << "NO\n";
	
}