BOJ-1514-자물쇠

필요한 지식

1. 동적계획법

접근

DP[i][x][y][z][d]:i번째 인덱스를 x번, i+1인덱스를 y번, i+2인덱스를 z번, d방향(0:뒤,1:앞)으로 돌렸을 떄 필요한 최소 회전 수 로 정의 했다.

• 문제 접근에있어서 d가 나타내는 방향성의 필요성에 대해 많이 헷갈렸던 문제다 지금와서 생각해보면 당연하지만..
• 현재 상태가 1이고 목표가 4로 만드는 것이라면 앞쪽으로 3칸을 한번만에 움직이면 되지만 방향성이 없는 경우 뒤쪽으로 도는 경우를 먼저 살피게된다면 dp[i][x][y][z]에 뒤쪽으로 3번만에 탐색한 경우의 값이 채워져있을 것이다. 그 후 앞쪽으로 도는 경우로 돌아왔을 때, dp[i][x][y][z]에 채워져있는 값을 리턴해주고 계산하지 않는다.
• 따라서 현재의 값이 앞쪽으로 회전해서 온건지, 뒤쪽으로 회전에서 온건지를 구분하는 인덱스가 하나 필요하다.

코드(C++)

#include <bits/stdc++.h>

#define FIO ios_base::sync_with_stdio(false), cin.tie(),cout.tie();
using namespace std;
int n, dp[101][10][10][10][2];
string from, to;

int MOD(int a, int b, int c) {
    return c > 0 ? (a + b + 20) % 10 : (a - b + 20) % 10;
}

int go(int idx, int x, int y, int z, int d) {
    if (idx == n) return 0;
    int &ret = dp[idx][x][y][z][d];
    if (ret != -1) return ret;
    ret = 1e9;
    if ((from[idx] - '0' + x + 20) % 10 == to[idx] - '0')
        return ret = min(go(idx + 1, y, z, 0, !d), go(idx + 1, y, z, 0, d));


    for (int k = 1; k <= 3; k++) {
        ret = min(ret, go(idx, MOD(x, k, d), y, z, d) + 1);
        ret = min(ret, go(idx, MOD(x, k, d), MOD(y, k, d), z, d) + 1);
        ret = min(ret, go(idx, MOD(x, k, d), MOD(y, k, d), MOD(z, k, d), d) + 1);
    }
    return ret;
}

int main() {
    FIO;
    cin >> n;
    cin >> from >> to;
    memset(dp, -1, sizeof(dp));
    cout << min(go(0, 0, 0, 0, 0), go(0, 0, 0, 0, 1));
    return 0;
}

결과