백준 1514번 : 자물쇠 - DP

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

1514번: 자물쇠

#include <bits/stdc++.h>

#define MX 101
using namespace std;

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


int dpf(int now, int x, int y, int z) {
    if (now == N) return 0;
    int &ret = dp[now][x][y][z];
    if (ret != -1) return ret;

    ret = 1e9;

    //현재 다른 칸 수
    int df = (B[now] - x + 10) % 10;
    //돌려야 할 칸 수 왼쪽, 오른쪽
    int d[2] = {df, 10 - df};

    // x는 d[0] 이나 d[1]만큼 돌리고, y는 0~d[0] 0~d[1] 만큼 돌릴 수 있고, z는 0~j만큼 돌릴 수 있다.
    for (int i = 0; i <= 1; i++) {
        for (int j = 0; j <= d[i]; j++) {
            for (int k = 0; k <= j; k++) {
                //x를 왼쪽으로 돌리는 경우와 오른쪽으로 돌리는 경우를 구분
                int yy = (y + (i ? -j : j) + 10) % 10;
                int zz = (z + (i ? -k : k) + 10) % 10;

                //전체 돌리는 횟수 계산
                int val = dpf(now + 1, yy, zz, A[now + 3]);
                val += ((d[i] - j + 2) / 3 + (j - k + 2) / 3 + (k + 2) / 3);
                ret = min(ret, val);
            }
        }
    }
    return ret;
}


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

    cin >> N >> AC >> BC;
    memset(dp, -1, sizeof(dp));

    for (int i = 0; i < N; i++) {
        A[i] = AC[i] - '0';
        B[i] = BC[i] - '0';
    }

    cout << dpf(0, A[0], A[1], A[2]) << '\n';
    return 0;
}