백준 15312번: 이름 궁합 (C++)

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

15312번: 이름 궁합

---

Solved By: DP

 

 

#include <iostream>
#include <vector>
using namespace std;

int base[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(){
    string a, b; cin >> a >> b;
    vector<vector<int>> cache(a.length() * 2, vector<int>(a.length() * 2));
    for(int i = 0; i < a.length(); i++){
        cache[0][i * 2] = (base[a[i] - 'A']);
    }
    for(int i = 0; i < b.length(); i++){
        cache[0][i * 2 + 1] = (base[b[i] - 'A']);
    }
    
    int temp = a.length() * 2 - 1;
    for(int i = 1; i < a.length() * 2; i++){
        //cout << i << '\n';
        for(int j = 0; j < temp; j++){
            cache[i][j] = (cache[i - 1][j] + cache[i - 1][j + 1]) % 10;
            //cout << cache[i][j] << ' ';
        }
        //cout << '\n';
        temp--;
    }
    
    cout << cache[a.length() * 2 - 2][0];
    cout << cache[a.length() * 2 - 2][1];
    return 0;
}