[BOJ 20047, C++] 동전 옮기기

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

20047번: 동전 옮기기

 

알고리즘학회 soo7652, kimtaehyun98님의 풀이를 들었음

투포인터로 접근 했었는데, N의 값이 작으면 걍 DP부터 생각해보는게 나은 것 같음. 참고로 투포인터를 사용하면 S[idx1] == T[idx2]일 때, idx1 += 1, idx2 += 1이 아닌 선택한 동전을 S에 넣고 idx2+=1을 하는 방법을 구현하기가 매우 어렵게 됩니다.

 

 

풀이

간단한 문제 풀이를 생각해보면 왼쪽에서부터 S와 T를 하나씩 비교해보다가 서로 다른 문자인 경우에는 선택한 두 동전중 하나를 사용하여 S에 넣어주면 되고, 서로 같은 문자인 경우에는 다음 인덱스로 넘어가거나 선택한 두 동전중 하나를 사용하여 S에 넣어주는 방법을 생각해볼 수 있습니다.

 

이때 선택한 두 동전을 넣는 경우의 수는 동전의 순서가 정해져있으므로 (선택한 동전을 S에 넣지 않을 때), (첫 번째 동전만 S에 넣었을 때), (두 번째 동전까지 S에 넣었을 때) 세 가지 방법만 존재합니다.

거기다가 n의 값이 최대 10,000이기 때문에 모든 경우의 수를 확인하는 배열을 생각해보면 dp[10,000][3]이므로 메모이제이션도 사용해볼만 합니다.

 

함수의 이름은 go(int x, int idx, int y)로 뒀는데, x는 S의 인덱스 번호, y는 선택한 동전을 넣은 개수, y는 T의 인덱스 번호입니다.

만약 S[x] == T[y]라면 go(x+1, idx, y+1)을 하여 다음 인덱스로 넘어가게 해줄 수 있고, coin[idx] == T[y]라면 선택한 동전을 S에 넣어줘서 go(x, idx+1, y+1)을 해줄 수도 있습니다.

마지막에는 y == n이 되고, idx == 2가 된다면 두 동전을 모두 S에 넣어서 T로 변환했다는 것이니 1을 반환하고, 아니라면 0을 반환하게 하여 go(0, 0, 0) = 1이면 YES를 출력하고, go(0, 0, 0) = 0이라면 NO를 출력해주면 됩니다.

 

코드

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
using ll = long long;
 
const int N = 10001;
int n, a, b, dp[N][3];
string s, t;
vector<char> S, T;
char arr[3];
 
int go(int x, int idx, int y) {
    if (y == n) {
        if (idx == 2) return 1;
        else return 0;
    }
 
    int& ret = dp[y][idx];
    if (ret != -1) return ret;
 
    ret = 0;
    if (x < n - 2 && S[x] == T[y]) ret = max(ret, go(x + 1, idx, y + 1));
    if (idx < 2 && arr[idx] == T[y]) ret = max(ret, go(x, idx + 1, y + 1));
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(dp, -1, sizeof(dp));
 
    cin >> n;
    cin >> s;
    cin >> t;
    cin >> a >> b;
 
    arr[0] = s.at(a);
    arr[1] = s.at(b);
 
    for (int i = 0; i < n; i++) {
        if (i == a || i == b) continue;
        S.push_back(s.at(i));
    }
    for (int i = 0; i < n; i++) {
        T.push_back(t.at(i));
    }
 
 
    if (go(0, 0, 0)) cout << "YES" << endl;
    else cout << "NO" << endl;
}