백준 13392번 : 방법을 출력하지 않는 숫자 맞추기 - DP

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

13392번: 방법을 출력하지 않는 숫자 맞추기

#include <bits/stdc++.h>

#define MX 10003
using namespace std;

int N, dp[MX][11];
char A[MX], B[MX];


int dpf(int num, int left) {
    int &ret = dp[num][left];
    if (ret > 0) return ret;
    if (num == N) return 0;

    int lcnt = ((A[num] - B[num]) - left + 20) % 10;
    int rcnt = 10 - lcnt;

    return ret = min(dpf(num + 1, (left + lcnt) % 10) + lcnt, dpf(num + 1, left) + rcnt);
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> B >> A;
    cout << dpf(0, 0) << '\n';
}