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

Algorithm/problem

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

DingCoDing 2022. 12. 10. 14:28

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

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

아래 그림과 같이 N개의 회전이 가능한 숫자 나사가 아래위로 연결되어 있다. 가장 위에 있는 숫자나사는 숫자나사 1이고 가장 아래에 있는 숫자나사는 숫자나사 N이다. 모든 숫자나사는 각각 10

www.acmicpc.net

#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';
}