- 컴퓨터융합학부
- BOJ 30027
- hhs2003
- boj 30788
- Delaunay triangulation
- 누텔라트리(hard)
- 수열과 쿼리 43
- BOJ 30026
- 느리게 갱신되는 세그먼트 트리
- 냅색
- boj23054
- 알고리즘
- fortune's algorithm
- 2023 SW - IT Contest
- Dynamic Programming
- 2023 Engineering Pair
- 오일러투어트리
- CodeForces
- Sakura Reflection
- 백준
- 세그먼트 트리
- 27114
- BOJ 30028
- BOJ17139
- BOJ 31226
- BOJ 30029
- dx dy
- 27173
- 충남대학교 2023 SW - IT
- voronoi diagram
알고리즘 일지
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)$ 입니다.
'알고리즘 풀이' 카테고리의 다른 글
BOJ 9616 - 홀수 정사각형 (0) | 2024.08.03 |
---|---|
EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2) D. World is Mine (2) | 2024.07.20 |
BOJ 23054 - 누텔라 트리 (Hard) (0) | 2024.05.21 |
BOJ 17139 - 초라기와 쿼리 (0) | 2024.04.09 |
BOJ 31226 - 고슴도치 그래프 2 (0) | 2024.02.29 |