BOJ 백준 20047번 동전 옮기기

 

BOJ 백준 20047 동전 옮기기

 

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

20047번: 동전 옮기기

 

두 개의 동전을 서로 순서를 바꾸지 않고 자리를 이동하여 문제에서 주어지는 동전 배치를 만들 수 있는지 묻는 문제이다.

 

학회에서 ACM ICPC 예선을 준비하면서 팀원과 같이 풀었던 문제이다. 처음에는 Queue를 이용하여 푸는 구현 문제인 줄 알고 시도했는데, 계속 채점을 돌려봐도 86퍼센트에서 틀렸다고 떠서 접근 자체가 틀렸음을 직감했다. 뒤늦게 다시 풀어봤는데 결국 다이나믹 프로그래밍(Dynamic Programming)으로 풀 수 있는 문제였다.

 

 

 

메모이제이션 할 배열 dp를 아래와 같이 정의했다.

 

dp[i][j]: i번째 원소까지 봤을 때 이동해야 하는 동전을 j개 이동하여 문자열 T[0:i]를 만들 수 있는지 여부

 

여기서 T[0:i]는 주어지는 동전 배치 문자열 T의 0번째부터 i번째까지의 부분문자열이다.

 

구현의 편의를 위해 동전을 이동하지 않고 제자리에 가만히 두는 경우도 해당 동전을 자신의 자리로 이동하는 것으로 전제한다. 즉, 문자열 S의 모든 원소를 다 봤을 때 이동했어야 하는 동전은 무조건 2개여야 한다.

 

 

 

그런데 이동하기 전의 기존 문자열 S에서 이동하는 동전 두 개에 대응하는 문자를 제외한 새로운 문자열 S’를 가지고 문자열 T와 비교하며 배열 dp를 업데이트 해야 하는데, 이렇게 고려하지 않고 단순히 문자열 S를 가지고 비교하면 이동해야 하는 동전 두 개에 대한 처리가 곤란해진다. 위의 정리 노트의 예를 보면 이해하기 쉽다.

 

 

 

배열 dp의 정의를 구현상 좀 더 쉽게 바꾸면 다음과 같다.

 

Two: 이동해야 하는 동전 두 개에 대한 문자열

dp[i][status]: 문자열 T의 i번째 원소까지 봤을 때 동전한 이동 상태가 status인 경우가 가능한지

 

status가 0인 경우: Two의 아무런 동전 이동하지 않은 상태

status가 1인 경우: Two[0](첫 번째 동전)만 이동한 상태

status가 2인 경우: Two[0]과 Two[1](첫 번째와 두 번째 동전) 모두 이동한 상태

 

 

 

즉, 관점을 바꿔서 생각해보면 문자열 S’에 Two의 원소를 순서에 맞도록 알맞게 배치하여 문자열 T를 만들 수 있는지를 판단하는 문제가 된다. 문자열 S’와 T 각각을 가리키는 인덱스 idx1와 idx2를 이동하면서 탐색하는 Top-Down 방식의 함수를 구현했다.

 

 

 

1. T[idx2]에 Two[status]를 배치하는 경우

T[idx2] == Two[status]이면

→ T[idx2]에 Two[status]를 배치하고 S’[idx1]와 T[idx2 + 1] 이어서 비교

 

dp[idx2][status] |= go(idx1, idx2 + 1, status + 1)

 

 

2. T[idx2]에 배치하지 않는 경우

S’[idx1] == T[idx2]이면

→ S’[idx1 + 1]와 T[idx2 + 1] 이어서 비교

 

dp[idx2][status] |= go(idx1 + 1, idx2 + 1, status)

 

 

3. Base Case 

idx2 == n일 때

status == 2이면(동전 두 개 다 배치한 경우) → 1 반환

status < 2이면 → 0 반환

 

#include <iostream>
#include <cstring>
#include <string.h>
#include <algorithm>
using namespace std;

const int N_MAX = (int)1e4;

int n, l, r;
int dp[N_MAX][3];
string s, t, two;

int go(int idx1, int idx2, int status){
    int& ret = dp[idx2][status];
    if (ret != -1){
        return ret;
    }
    
    if (idx2 == n){
        if (status == 2){
            return ret = 1;
        }
        return ret = 0;
    }
    
    ret = 0;
    
    if (status < 2){
        if (t[idx2] == two[status]){
            ret |= go(idx1, idx2 + 1, status + 1);
        }
    }
    
    if (s[idx1] == t[idx2]){
        if (idx1 < n - 2){
            ret |= go(idx1 + 1, idx2 + 1, status);
        }
    }

    return ret;
}

int main(){
    cin.tie(NULL);
    cin.sync_with_stdio(false);
    
    memset(dp, -1, sizeof(dp));
    
    string x;
    cin >> n >> x >> t >> l >> r;

    two += x[l];
    two += x[r];

    for (int i = 0; i < n; i++){
        if (i != l && i != r){
            s += x[i];
        }
    }
    
    if (go(0, 0, 0)){
        cout << "YES\n";
    }
    else {
        cout << "NO\n";
    }
    
    return 0;
}