🖊️ 문제

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

---

🖊️ 풀이

이름 궁합을 보는건데,,
다른건 다 괜찮은데 계속 생겨나는 숫자들을 어디에 저장해둘까?

벡터에 계속 저장해줄까 하다가
그냥.. 최대 4000개정도니까 dp 2차원 배열을 선언해두고 거기다가 저장해줬다.

왜냐하면
dp[idx+1][i] = dp[idx][i] + dp[idx][i+1] 이므로 ~!

다만,
출력이 앞자리가 0일때도 두 자리로 출력해야 하므로 string 형으로 바꿔서 출력해줬다!

실5답게 크게 어렵지 않았던 문젱 ~

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

int arr[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 dp[4010][4010];

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	string a;
	string b;
	cin >> a;
	cin >> b;
	
	for (int i = 0; i < a.size(); i++) {
		int idxA = a[i] - 'A';
		int idxB = b[i] - 'A';
		dp[0][i * 2] = arr[idxA];
		dp[0][i * 2 + 1] = arr[idxB];
	}

	int cnt = a.size() * 2;
	for (int idx = 0 ; idx < cnt - 2 ; idx++) {
		for (int i = 0; i < cnt - 1; i++) 
			dp[idx + 1][i] = (dp[idx][i] + dp[idx][i + 1]) % 10;
	}
	string result = "";
	result += dp[cnt - 2][0] + '0';
	result += dp[cnt - 2][1] + '0';

	cout << result << endl;
}