[백준 15312번] [동적 계획법] 이름 궁합

Approach

한 글자가 숫자에 하다씩 매핑되는 양상이므로 replace 등의 함수를 활용하는 것이 아니라, ASCII를 활용하여 대문자와 주어진 숫자를 하나씩 매핑해주는 방식을 사용해주면 된다.

 

추가적으로 계산이 초기 문자열의 길이 * 2 - 1 부터 시작해서 1개씩 줄어드는 양상이고, 처리 순서가 앞에서 뒤로만 가고 있으므로

큐 자료구조를 활용해주면 쉽게 처리할 수 있다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int dp[26] = {3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1};

int main(void){
    fastio;
    string a, b;
    cin >> a >> b;

    int s_size = a.size();
    queue<int> q;
    for(int i = 0; i < s_size; i++){
        q.push(dp[a[i] - 'A']);
        q.push(dp[b[i] - 'A']);
    }

    int recur = 2 * s_size - 1;
    while(q.size() != 2){
        for(int i = 0; i < recur; i++){
            int f = q.front();
            q.pop();
            int b = q.front();
            q.push((f + b) % 10);
        }
        q.pop();
        recur--;
    }

    int result_f = q.front();
    q.pop();
    int result_b = q.back();

    cout << result_f << result_b << "\n";
    return 0;
}