[BAE/<JOON> 문제풀이] 20047. 동전 옮기기

핵심::
구현(?) 풀이
DP 태그 붙어 있어서 점화식 찾으려다 못찾고
결국 재귀로 풀이했다. ( Top Down 방식으로 풀이 했기 때문에 DP가 맞긴 하다 )

풀이::
이동 가능한 2개의 동전 배열과 초기 동전 배열에서 그 동전 2개를 뺀 배열 2개를 만든다

ex)
6
oooxxx
oxoxox
1 2
=> 이 경우, 각각의 배열은 다음과 같이 분리 된다.
arr1 = oxxx
arr2 = oo

이 분리된 배열들을 앞쪽부터 적절히 순서를 섞어 주어진 2번째 배열(예제 oxoxox)을 만들 수 있는지 여부를 검사하면 된다.

이 부분은 그냥 구현 쪽이고 두 배열의 몇번째 인덱스를 사용했을 때 결과가 정해지는지 여부만 DP 배열에 따로 저장했다.

의견::
DP 정해가 뭔지 궁금하다.

이게 왜 DP지

 

코드::

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

using namespace std;

int dp[10001][3];
int a1[9999];
int a2[3];
int arr[10001];
int n;

int r(int c1, int c2) {
    int& ret = dp[c1][c2];
    if(ret != 0) return ret;
    int cur = c1 + c2;
    if(cur == n) {
        return ret = 1;
    }
    int r1 = -1, r2 = -1;    
    if(c1 < n - 2) {
        if(arr[cur + 1] == a1[c1 + 1]) {
            r1 = r(c1 + 1, c2);
        }    
    }
    if(c2 < 2) {
        if(arr[cur + 1] == a2[c2 + 1]) {
            r2 = r(c1, c2 + 1);
        }
    }

    return ret = (r1 > r2 ? r1 : r2);
}

int main() {
    cin >> n;
    string s1, s2;
    cin >> s1;    
    cin >> s2;
    for(int i=1;i<=n;i++) {
        arr[i] = s2[i - 1];
    }
    int n1, n2;
    cin >> n1 >> n2;
    n1 += 1;
    n2 += 1;
    a2[1] = s1[n1 - 1];
    a2[2] = s1[n2 - 1];
    for(int i=1;i<=n;i++) {
        a1[i] = s1[i - 1];
    }
    for(int i=n2;i<=n;i++) {
        a1[i] = a1[i + 1];
    }
    for(int i=n1;i<=n;i++) {
        a1[i] = a1[i + 1];
    }

    int ret = r(0, 0);
    cout << ((ret == 1) ? "YES" : "NO");

    return 0;
}