백준 20047(동전 옮기기)

www.acmicpc.net/problem/20047

20047번: 동전 옮기기

dp로 풀자 

밑에 ㅈㄴ 더러운 풀이임 걍 스킵추천 

------------------------------------------------------------------------------------------------------

dp로 풀 수 있다는데 아직 생각을 해보질 않아서 감은 안온다. 근데 그리디로도 가능하다 

모든 문제가 그리디로 가능할 수 있다고 말할지도 모르겠지만 이 문제는 생각보다 간단한 구조의 그리디이다. 

 

두개를 빼서 그 순서를 유지한 채 옮길 수 있다. 

 

이 순서를 유지한다는 거에 중심을 두고 생각을 해보자 

 

먼저 뺀 것을 무조건 먼저 넣어야 한다.

 

어디에 넣어야 할까

 

만약 결과를 같게 만드는것이 목표라면 당연히 처음 다른곳에 넣어야 한다는게 자명하다. 

 

처음 다른 곳에 삽입을 하고나서 또 두번째꺼를 넣는다고 생각해보자 

그렇게 되면 처음 다른곳은 이전에 했던 곳 보다 크거나 같은 곳에 위치할 것이다.

 

만약에 같은 곳이라면 절대 만들 수 없는 모양이라서 그렇게 된 것이다. 

 

근데 우리가 여기서 봐야할 부분이 또 있다. 

 

만약에 2개를 뺀 배열에서 비교한 모든 부분이 같으면 어떻게 되느냐이다. 

 

이 부분이 헷갈려서 계속 생각을 해봤는데 결과적으로 한가지 케이스가 나오는 것 같다.

 

뺀 두개와 남은 두개가 순서가 다른 경우 

만약에 뺀 두개와 남은 두개가 순서가 같으면 상관 x

 

xox 

xox

0 1 과 

 

xox

xxo

1 2

 

1번 케이스에서 두 가지를 빼면 

 

xo

 

x

xox

가 된다 

 

1번 케이스는 앞전까지 모두 같으면서, 원래 주어진 두가지 배열도 같은 모양일때이다.

 

2번 케이스는 

 

ox

 

x

xxo

 

2번 케이스는 앞전까지 모두 같으면서, 원래 주어진 두가지 배열이 다른 모양일때이다. 

 

1번은 당연히 pass하고 

2번은 fail시키면 된다. 

 

위의 케이스가 아닌 다른 반례가 될 수 있는 케이스가 있는가를 생각해보았는데, 없는 것 같다. 

 

그래서 그냥 이렇게 끝내려고 한다. 

 

아마도 없겠지 더이상의 반례는 .. ?

---------------

또 있다.. 

3

xxo

xox

0 2

생각좀 더 해보고 코드 수정후에 올리겠다. 

 

그 앞까지 모두 같은 경우에 그 직전에 두개 모두 넣어서 같은 경우를 넣어서 수정했다. 

생각해보니깐 진짜 거기가 끝인 거 같은데.. 

 

코드가 너무 너저분 해졌다. 

차라리 체크 코드를 생각해볼걸 그랬나 

 

#include<iostream>
using namespace std;
#define MAX 10005

char a[MAX], b[MAX];
char tmp[MAX], tmp2[MAX], tmp3[MAX], tmp4[MAX];
int n;
bool check1, check2;


int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}

	int idx1, idx2;
	cin >> idx1 >> idx2;
	bool sameflag = true;
	for (int i = 0; i < n; i++) {
		if (a[i] != b[i]) {
			sameflag = false;
			break;
		}
	}
	if (sameflag) {
		cout << "YES";
		return 0;
	}

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (i == idx1 || i == idx2)continue;
		tmp[cnt++] = a[i];
	}

	for (int i = 0; i < n - 2; i++) {
		if (tmp[i] != b[i]) {
			check1 = true;
			for (int j = 0; j < i; j++) {
				tmp2[j] = tmp[j];
			}
			tmp2[i] = a[idx1];
			for (int j = i + 1; j < n - 1; j++) {
				tmp2[j] = tmp[j - 1];
			}
			break;
		}
	}

    // 2개뺀 배열과 비교 배열과 모조리 같은 경우. 
    // 두 케이스로 분류 (순서 유지한채로)
    // 1. 뒤에 넣는 경우
    // 2. 앞에 넣는 경우 
	if (!check1) {
		int i;
		for (i = 0; i < n - 2; i++) {
			tmp2[i] = tmp[i];
			if(i<n-3)
				tmp4[i] = tmp[i];
		}
		tmp4[n - 3] = a[idx1];
		tmp4[n - 2] = a[idx2];
		tmp4[n - 1] = a[n - 3];

		tmp2[n - 2] = a[idx1];
		tmp2[n - 1] = a[idx2];
		bool chk1 = true;
		bool chk2 = true;
		for (int i = 0; i < n; i++) {
			if (tmp2[i] != b[i]) {
				chk1 = false;
			}
			if (tmp4[i] != b[i]) {
				chk2 = false;
			}
		}
		if (chk1 || chk2) {
			cout << "YES";
			return 0;
		}
		else {
			cout << "NO";
			return 0;
		}

	}


	for (int i = 0; i < n - 1; i++) {
		if (tmp2[i] != b[i]) {
			check2 = true;
			for (int j = 0; j < i; j++) {
				tmp3[j] = tmp2[j];
			}
			tmp3[i] = a[idx2];
			for (int j = i + 1; j < n; j++) {
				tmp3[j] = tmp2[j - 1];
			}
			break;
		}
	}
	if (!check2) {
		int i;
		for (i = 0; i < n - 1; i++) {
			tmp3[i] = tmp2[i];
		}
		tmp3[n - 1] = a[idx2];
	}
	bool chk = true;
	for (int i = 0; i < n; i++) {
		if (tmp3[i] != b[i]) {
			chk = false;
			break;
		}
	}
	if (chk) {
		cout << "YES";
	}
	else cout << "NO";
}