백준: 20047

</br> 계속 풀이
</br>

20047: 동전 옮기기

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

예선 당시 처음에 그리디로 생각해서 쭉 가다가 틀린 거 나오면 넣어 주고 하면 되지 않을까요?? 했는데 계속 틀렸다
반례가 있음…

ex) 
3
xox
xox
0 1
(답: YES)

그리디로 풀면
x, o
x
xox
처음 x가 맞아서 그냥 넘어가면 못 만들게 된다

그렇게 쉬우면 나올 리가 없겠지
그런데 I번도 나온 걸 보면 문제 난이도를 알 수가 없다는 게 또 그렇다

아무튼 요는 지금 둘이 똑같아도 동전을 한 번 넣어 봐 줘야 한다.

방법 1. 재귀

#include <bits/stdc++.h>

using namespace std;

string s1, s2;
char c[2];
int n;

bool func(int start, int skip){
    if( start + skip == n ) return true;
    if( s1[start] == s2[start+skip] )
        if( func(start+1, skip) ) return true;
    if( skip == 2 ) return false;
    if( c[skip] == s2[start+skip] )
        if( func(start, skip+1) ) return true;
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string tmp;
    cin >> n >> tmp >> s2;
    int ind1, ind2;
    cin >> ind1 >> ind2;

    c[0] = tmp[ind1], c[1] = tmp[ind2];

    for(int i = 0; i < n; i++){
        if( i != ind1 && i != ind2 ) s1 += tmp[i];
    }

    if( func(0, 0) ) cout << "YES\n";
    else cout << "NO\n";

}

s1에서 동전 2개를 빼서 c[]에 저장한다
s2와 s1이 다르면 현재 넣을 수 있는 동전과 비교해 보고, 같다면 동전을 넣어 스킵할 수 있다.

</br>

방법 2. dp

#include <bits/stdc++.h>

using namespace std;

string s1, s2;
char c[2];
int n;
int dp[10001][3];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string tmp;
    cin >> n >> tmp >> s2;
    int ind1, ind2;
    cin >> ind1 >> ind2;

    c[0] = tmp[ind1], c[1] = tmp[ind2];

    s1 += ' ';
    s2.insert(0, " ");
    for(int i = 0; i < n; i++){
        if( i != ind1 && i != ind2 ) s1 += tmp[i];
        dp[i][0] = 0;
        dp[i][1] = 0;
        dp[i][2] = 0;
    }

    dp[0][0] = 1;
    dp[0][1] = 0;
    dp[0][2] = 0;
    for(int i = 1; i <= n; i++){
        if( dp[i-1][0] ){
            if( s1[i] == s2[i] ) dp[i][0] = 1;
            if( c[0] == s2[i] ) dp[i][1] = 1;
        }
        if( dp[i-1][1] ){
            if( s1[i-1] == s2[i] ) dp[i][1] = 1;
            if( c[1] == s2[i] ) dp[i][2] = 1;
        }
        if( dp[i-1][2] ){
            if( s1[i-2] == s2[i] ) dp[i][2] = 1;
        }
    }

    if( dp[n][2] ) cout << "YES\n";
    else cout << "NO\n";

}

dp를 편하게 계산하려고 s1과 s2 앞에 공백을 하나 넣어 인덱스는 1부터하게 했다
dp[n][3]으로, 현재 동전 상태를 저장한다. 0은 넣은 동전 없음, 1은 왼쪽 동전 넣음, 2는 오른쪽 동전까지 다 넣음
이거는 s2 기준으로 인덱스를 해야 편하다
일단 dp[0][0]이 제일 처음 상태이므로 1로 하고, 나머지는 0으로 한다.
만약 dp[i-1][0]이 1이라면, 전 단계에서 동전을 하나도 안 쓴 게 가능하다는 말이다. 그 때 s1과 s2 비교 결과가 같으면 dp[i][0]도 1이다. 그리고 만약 왼쪽 동전과 s2가 같으면, 이 경우도 넣어주기 위해 dp[i][1]을 1로 한다.
dp[i-1][1]의 경우도 비슷하고, 만약 dp[i-1][2], 즉 동전을 다 쓴 경우라면 s1과 s2 비교 결과가 같을 때만 가능하다.
마지막엔 두 동전을 다 썼을 때만 가능하므로, dp[n][2]가 1인지 확인하면 된다.

인덱스가 헷갈려서 dp 풀이는 여러 번 틀렸다
</br>

---

1인분을 목표로
</br>