BOJ 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)$ 입니다.