2494번: 숫자 맞추기

https://www.acmicpc.net/problem/2494

#include<cstdio>
int n, a[10001], b[10001], dp[10001][10];
struct st {
    int l, r, p;
}fr[10001][10];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%1d", a + n - i);
    for (int i = 0; i < n; i++) scanf("%1d", b + n - i);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 10; j++) {
            dp[i][j] = dp[i - 1][j] + (a[i] - b[i] - j + 20) % 10;
            fr[i][j] = { 0,-(a[i] - b[i] - j + 20) % 10,j };
        }
        for (int j = 1; j < 21; j++) if (dp[i][j % 10] > dp[i][(j - 1) % 10] + 1) {
            dp[i][j % 10] = dp[i][(j - 1) % 10] + 1;
            fr[i][j % 10] = fr[i][(j - 1) % 10];
            fr[i][j % 10].l++;
        }
    }
    printf("%d\n", dp[n][0]);
    for (int i = n, t = 0; i; t = fr[i--][t].p) printf("%d %d\n%d %d\n", n + 1 - i, fr[i][t].l, n + 1 - i, fr[i][t].r);
    return 0;
}