BOJ 2494 숫자 맞추기

1 개요

BOJ 2494 숫자 맞추기
2 C++

#include <bits/stdc++.h>
using namespace std;

struct T {
    int x, y, m;
};

int N;
string asis, tobe;
int dp[10004][11];
T child[10004][11];

int dfs(int x, int turn) {
    int &ret = dp[x][turn];
    if (x == N) return 0;
    if (ret) return ret;

    int l = (tobe[x] - asis[x] - turn + 20) % 10;
    int r = 10 - l;

    int left = dfs(x + 1, (turn + l) % 10) + l;
    int right = dfs(x + 1, turn) + r;

    T &baby = child[x][turn];
    if (left < right) baby = {x + 1, (turn + l) % 10, l};
    else baby = {x + 1, turn, -r};
    return ret = min(left, right);
}

void solve() {
    cout << dfs(0, 0) << '\n';
    int x = 0, turn = 0;
    for (int i = 1; i <= N; i++) {
        T &cur = child[x][turn];
        cout << i << ' ' << cur.m << '\n';
        x = cur.x;
        turn = cur.y;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> asis >> tobe;
    for (int i = 0; i < N; i++) {
        asis[i] -= '0';
        tobe[i] -= '0';
    }
    solve();
 }