현재 자물쇠 상태를 원하는 자물쇠 상태로 최소로 돌렸을 때 몇 번만에 할 수 있는지 구하는 문제입니다.
DP 문제입니다.
BOJ - 13392 이 문제가 생각나는 문제였습니다.
DP[현재 디스크 번호][현재 디스크 번호의 상태][현재 디스크 번호 + 1의 상태][현재 디스크 번호 + 2의 상태] = 최소 횟수
이렇게 저장하게 되면 중복되는 경우의 시간을 줄일 수 있습니다.
현재 디스크 번호에서 원하는 상태로 맞추려는 돌리는 횟수를 X라고 하겠습니다.
인접한 현재 디스크 번호 + 1은 0~X의 횟수를 돌릴 수 있습니다.
현재 디스크 번호 + 2은 0~번호 + 1에서 돌린 횟수만큼 돌릴 수 있습니다.
시계 방향과 반 시계 방향 두 가지 방법 모두 횟수를 구해봐야 합니다.
이 모든 경우를 보면서 상황마다 횟수를 구하고 그 횟수 중에서 최소를 저장하면 됩니다.
위에서 언급한 문제와 비슷한 것 같아 생각보다 쉽게 풀 수 있었습니다.
역시 DP는 많은 유형을 풀어보는 것이 좋을 것 같네요!
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int main() {
FIO;
int n; cin >> n;
int a[105] = {}, b[105] = {};
string s1, s2; cin >> s1 >> s2;
FOR(i, 1, n) a[i] = s1[i - 1] - '0';
FOR(i, 1, n) b[i] = s2[i - 1] - '0';
int dp[105][15][15][15];
memset(dp, -1, sizeof(dp));
function <int(int, int, int, int)> DP = [&](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 ck = (b[now] - x + 10) % 10;
int d[2] = { ck, 10 - ck };
FOR(i, 0, 1) FOR(j, 0, d[i]) FOR(k, 0, j) {
int yy = (y + (i ? -j : j) + 10) % 10;
int zz = (z + (i ? -k : k) + 10) % 10;
int val = DP(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;
};
cout << DP(1, a[1], a[2], a[3]) << '\n';
return 0;
}