백준 20047 동전옮기기

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

문제 설명

동전 두 종류가 있을 때
임의의 동전 배열이 주어지고 ex) oxoxoooxxoxo
선택하는 두 동전의 위치가 주어질 때
이 동전을 순서를 바꾸지 않고 끼워넣어 주어지는 다른 배열을 만들 수 있는지 푸는 문제

문제 풀이

dp를 이용하여 해결

dp[x][y]

• x : 추가하는 동전 수 (0 ~ 2개)
• y : 만들어야하는 동전 배열 위치 (0 ~ n-1)

위의 배열이 있다고 하면...
dp[x][y]가 1이면 동전 x개를 추가하여 y까지의 동전배열을 만들 수 있다는 뜻

만약 뺴놓은 동전 배열이 tmp라고 하고, 동전이 빠진 배열이 s1, 만들어야하는 배열이 s2라고 한다면

• dp[x-1][y-1] ==1 && s2[y]==tmp[x-1] 을 만족한다면
  x-1 개의 동전을 사용하여 y-1 길이의 목표하는 동전 배열을 만들 수 있다면 -> x-1 번쨰의 동전과 y번쨰 동전이 같다면 빼놓은 동전을 사용하여 배열을 채울 수 있다
  -> dp[x][y] =1
• dp[x][y-1] == 1 && s2[y] == s1[y-x]
  x개의 동전을 사용하여 y-1 길이의 목표 배열을 만들 수 있다면
  -> y번쨰 동전과 빠진 동전 배열에서 끼워넣은 동전 수 x를 빼 s1[y-x]이 같다면 새 동전을 넣지 않더라도 dp[x][y]를 만족할 수 있다
  -> dp[x][y] =1

코드

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

//동전 2개 선택시 순서 유지하고 위치 이동 가능 
using namespace std;
int dp[3][10001];
int main(){
	int n;
	scanf("%d",&n);
	int t1,t2;
	//빼두었다가 꼭 필요하다면 넣는다
	
	string s1, s2;
	cin>> s1;
	cin >> s2;
	scanf("%d %d",&t1,&t2);
	char tmp[2];
	tmp[0] = s1[t1];
	tmp[1] = s1[t2];
	s1.erase(t1,1);
	s1.erase(t2-1, 1);
	
	for(int i=0;i<n-2;i++){
		if(s1[i] == s2[i]){
			dp[0][i] = 1;
		}else{
			break;
		}
	}
	if(tmp[0] == s2[0]){
		dp[1][0] =1;
	}
	if(tmp[0] == s2[0] && tmp[1] == s2[1]){
		dp[2][1] = 1;
	}
	for(int j=1;j<=2;j++){
		for(int i=1;i<n;i++){
			if((dp[j-1][i-1] == 1 && s2[i] == tmp[j-1]) || (dp[j][i-1] == 1 && s2[i] == s1[i-j])){
				dp[j][i] = 1;
			}
		}
	}
//	for(int i=0;i<3;i++){
//		for(int j=0;j<n;j++){
//			printf("%d",dp[i][j]);
//		}
//		printf("\n");
//	}
	if(dp[2][n-1] == 1){
		printf("YES");
		
	}else{
		printf("NO");
	}
	return 0;
}``