백준 [2494] 숫자 맞추기

문제 설명

문제 링크

http://icpc.me/2494

2494번: 숫자 맞추기

풀이

dp를 역추적하는 문제다.

백준 13392 방법을 출력하지 않는 숫자 맞추기 이 문제에서 역추적만 포함하면 된다.

dp를 호출할 때 왼쪽 자식에서 왔는지 오른쪽 자식에서 왔는지 체크를 해주면서 함수를 호출하면 된다.

코드

#include <cstdio>
#include <algorithm>

using namespace std;

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

char from[10004];
char to[10004];
int dp[10004][11], N;
T child[10004][11];

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

    int l = (to[n] - from[n] - turn + 20) % 10;
    int r = 10 - l;

    int turnLeft = dpf(n + 1, (turn + l) % 10) + l;
    int turnRight = dpf(n + 1, turn) + r;

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

int main() {
    scanf("%d", &N);
    scanf("%s", from);
    scanf("%s", to);
    for (int i = 0; i < N; i++) {
        from[i] -= '0';
        to[i] -= '0';
    }
    printf("%d\n", dpf(0, 0));
    
    int n = 0, turn = 0;
    for (int i = 1; i <= N; i++) {
        T &cur = child[n][turn];
        printf("%d %d\n", i, cur.m);
        n = cur.x;
        turn = cur.y;
    }
 }