BOJ 1514 - 자물쇠

 

 

문제 링크

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

 

문제 풀이

 

자물쇠를 돌려야 한다. 영향을 끼쳐서 나오는 경우의 수가 자물쇠의 3다이얼 밖에 안 되니 $10^3$ 정도이다.

자물쇠를 돌리는데에 있어서, 어떠한 유효한 방법이나 선택적 전략이 없기 때문에, 다이나믹 프로그래밍을 하며 모든 경우의 수를 시험해봐야 한다.

 

다이나믹 프로그래밍에서 어려운 점은 이런 까다로운 많은 분기에서의 dp의 정의라고 할 수 있다.

dp테이블을 잘 정의하는 것이 dp를 쉽게 푸는 길이라고 생각한다.

 

내가 정의한 dp는 다음과 같다.

 

$dp[N][i][j][k] $ 은 $N$번째 다이얼까지 맞췄을 때, $N+1$번째 다이얼이 $i$번, $N + 2$번째 다이얼이 $j$번, $N+3$다이얼이 $k$ 번째를 향하고 있을 때, 돌렸던 다이얼의 최소 코스트라고 할 수 있다.

 

즉, 최초 다이얼이 $\mbox{12312551512}\cdots$ 라면,

$$dp[0][1][2][3] = 0$$

라고 정의 할 수 있겠다.

 

dp 점화식은 생각보다 엄청나게 까다롭다.. 내가 라텍스 수식으로 쓸 엄두가 안 나서, 말로 대충 서술하겠다.

자물쇠를 돌릴 때, 유효한 방법이나 선택적 전략이 없다. 독자가 생각한 모든 그리디는 반례가 있다고 생각하면 되겠다.

 

따라서, $dp[N][i][j][k]$ 를 구할 때, $N$번째 다이얼이 맞춰지도록 하면서, $N+1$과, $N+2$번째 다이얼도 같이 돌려보는 모든 경우의 수를 시험해 봅시다.

 

#include<bits/stdc++.h>

using namespace std;

int dp[202][10][10][10];

string AA, BB;

int A[202], B[202], nums[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int costss[10] = {0, 1, 1, 1, 2, 2, 2, 1, 1, 1};

int main () {
    int N; cin >> N;
    cin >> AA >> BB;

    N+=5;
    AA += "00000";
    BB += "00000";

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

    fill_n(&dp[0][0][0][0], 101*1000, 1e9);

    dp[0][A[0]][A[1]][A[2]] = 0;

    for (int i=1;i<=N-5;i++) {
        //i 번째 자물쇠 푸는것. 1-based 0-based로 적어야함.

        for (int j : nums) {
            for (int k : nums) {
                for (int g : nums) {
                    int now = dp[i-1][j][k][g];
                    if (now == 1e9) continue;
                    for (int f1 : nums) for (int f2 : nums) for (int f3: nums) {
                        int cost = costss[f1] + costss[f2] + costss[f3];
                        if ((j + f1 + f2 + f3) % 10 != B[i-1]) continue;

                        int &x = dp[i][(k + f2 + f3) % 10][(g + f3) % 10][A[i+2]];
                        x = min(x, now + cost);
                    }
                }
            }
        }
    }

    cout << dp[N-5][0][0][0];
}

 

저는 현재 맞추고 있는 다이얼 인덱스의 +2를 임의로 접근하고 있으므로, 여유롭게 자물쇠 문자열에 "00000"씩 똑같이 붙여 줬습니다.

 

총합해서.. 6중포문이고, $\mbox{O}(N 10^6)$ 입니다.