숫자 맞추기

문제 링크

발상 & 점화식

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

역추적

DP 배열에 이전 인자를 저장하는 방식으로 역추적할 수 있다. 사용한 인자는 이전에 양의 방향으로 돌린 횟수와 자물쇠 인덱스인데, 자물쇠 인덱스는 항상 1씩 증가하므로 별도로 저장할 필요는 없다. 양의 방향과 음의 방향으로 돌렸을 때 비용이 적은 쪽의 인자와 그 때 발생한 비용을 저장하면 역추적할 수 있다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
struct node {
	int v = -1, c, p = -1;
};
int n; string s, d;
vector<vector<node>> dp;
int r(int c, int sp) {
	if (c == n) return 0;
	if (dp[c][sp].v != -1) return dp[c][sp].v;
	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);	
	dp[c][sp].c = s1 < s2 ? psp : -nsp; // 최적일 때 발생한 비용 저장
	dp[c][sp].p = s1 < s2 ? (sp + psp) % 10 : sp; // 최적일 때의 인자 저장
	return dp[c][sp].v = s1 < s2 ? s1 : s2;
}
void printpath(int c, int sp) { // 0, 0부터 역추적
	if (c == n) return;
	cout << c + 1 << " " << dp[c][sp].c << "\n";
	printpath(c + 1, dp[c][sp].p);
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n; dp = vector<vector<node>>(n + 1, vector<node>(10));
	cin >> s >> d; 	
	cout << r(0, 0) << "\n";
	printpath(0, 0);
	return 0;
}