BOJ 2494 숫자 맞추기

1 개요

BOJ 2494 숫자 맞추기

• 백준 온라인 저지 2494번 문제
• BOJ 47단계

2 C++

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

struct State {
    int pos, rotate, move;
};
int N;
char asis[10002];
char tobe[10002];
int minMoves[10004][11];
State nextState[10004][11];

int dfs(int pos, int rotate) {
    int &moves = minMoves[pos][rotate];
    if (pos == N) return 0;
    if (moves) return moves;

    int leftTurn = (tobe[pos] - asis[pos] - rotate + 20) % 10;
    int rightTurn = 10 - leftTurn;

    int leftMoves = dfs(pos + 1, (rotate + leftTurn) % 10) + leftTurn;
    int rightMoves = dfs(pos + 1, rotate) + rightTurn;

    State &next = nextState[pos][rotate];
    if (leftMoves < rightMoves) next = {pos + 1, (rotate + leftTurn) % 10, leftTurn};
    else next = {pos + 1, rotate, -rightTurn};
    return moves = min(leftMoves, rightMoves);
}

void solve() {
    cout << dfs(0, 0) << '\n';
    int pos = 0;
    int rotate = 0;
    for (int i = 1; i <= N; i++) {
        State &current = nextState[pos][rotate];
        cout << i << ' ' << current.move << '\n';
        pos = current.pos;
        rotate = current.rotate;
    }
}

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();
}