방법을 출력하지 않는 숫자 맞추기

문제 링크

발상

특정 자물쇠 인덱스에서 선택할 수 있는 동작은 2가지다.

1. 양의 방향으로 돌리기
2. 음의 방향으로 돌리기 양의 방향으로 돌릴 경우, 돌린 양만큼 다음 모든 인덱스들에 영향을 주게 된다. 자물쇠 상태를 일일이 저장하지 않아도 앞선 인덱스에서 양의 방향으로 돌린 횟수만 알 수 있으면 현재 자물쇠 상태를 알 수 있다. 따라서 인자는 자물쇠 인덱스와 현재 인덱스 앞에서 양의 방향으로 돌린 횟수의 합이다. 또한 각 인덱스마다 10개의 숫자가 있으므로 돌린 횟수의 합은 10으로 나눈 나머지만 저장해도 된다. 순차적으로 현재 인덱스의 자물쇠 숫자를 양과 음으로 돌려 목표값에 맞추며, ‘현재 인덱스를 맞추기 위해 돌려야 하는 횟수 + 양과 음으로 돌렸을 때 이후 추가로 돌려야 하는 횟수’의 합이 작은 것을 고르면 된다.

점화식

$$\{\begin{array}{l}{n}_{i,k}=\text{앞에서 양의 방향으로 k번 회전시킨 자물쇠를 i번째 위치에서 맞출 때 필요한 회전 수}\\ s_i=\text{자물쇠의 i번째 숫자}\\ d_i=\text{자물쇠의 i번째 목표 숫자}\end{array}$$ $$\begin{array}{rl}& psp=((d_i-(s_i+k))\mathrm{mod}10\text{ = 양의 방향으로 필요한 회전 수}\\ & n_{i,k}=\min (\{\begin{array}{l}{n}_{i+1,(k+psp)\mathrm{mod}10}+psp\\ n_{i+1,k}+(10-psp)\end{array})\end{array}$$

양의 방향으로 돌렸을 때, 음의 방향으로 돌렸을 때 2가지를 모두 수행해보고 더 작은 케이스를 선택한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int n; string s, d;
vector<vector<int>> dp;
int r(int c, int sp) {
	if (c == n) return 0;
	if (dp[c][sp] != -1) return dp[c][sp];
	int psp = (d[c] - '0' - (s[c] - '0' + sp) % 10 + 10) % 10;
	int nsp = 10 - psp;
	int s1 = r(c + 1, (sp + psp) % 10) + psp;	
	int s2 = (nsp == 10 ? 21e8 : r(c + 1, sp) + nsp);
	return dp[c][sp] = s1 < s2 ? s1 : s2;
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n; dp = vector<vector<int>>(n + 1, vector<int>(10, -1));
	cin >> s >> d; 	
	cout << r(0, 0);
	return 0;
}