[C++] 백준(BOJ) - 1514 : 자물쇠
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
세준이는 노트북을 누가 가져갈까봐 자물쇠로 잠가놓는다. 자물쇠는 동그란 디스크 N개로 구성되어 있다. 각 디스크에는 숫자가 0부터 9까지 숫자가 표시되어 있다. 디스크는 원형이기 때문에, 0과 9는 인접해 있다.
세준이는 한 번 자물쇠를 돌릴 때, 최대 세 칸을 시계 방향 또는 반시계 방향으로 돌릴 수 있다. 또, 최대 세 개의 인접한 디스크를 한 번에 돌릴 수 있다.
현재 자물쇠의 상태와 세준이의 비밀번호가 주어질 때, 자물쇠를 최소 몇 번 돌려야 풀 수 있는지 구하는 프로그램을 작성하시오.
자물쇠의 상태가 555이고, 세준이의 비밀번호가 464인 경우에, 각 디스크를 따로 따로 돌리면 3번 돌려야 한다. 하지만, 디스크 3개를 동시에 돌려서 444로 만들고, 2번째 디스크를 6으로 돌리면 2번만에 돌릴 수 있다.
입력
첫째 줄에 세준이의 비밀번호의 길이 (자물쇠의 크기) N이 주어진다. N은 100보다 작거나 같다. 둘째 줄에 현재 자물쇠의 상태가 주어지고, 셋째 줄에 세준이의 비밀번호가 주어진다.
출력
첫째 줄에 최소 몇 번을 돌려야 풀 수 있는지 구하는 프로그램을 작성하시오.
알고리즘
- DP
풀이
- 경우의 수
- 최대 3칸 / 최대 3번 / 회전(시계, 반시계) => 18가지
- dp 상태값 지정
- dp[인덱스][x][y][z][회전]
- idx가 n에 도달한 경우 재귀함수 종료
- 인덱스 기준 x가 맞춰졌다면 pos + 1 하고 x, y, z를 한 칸씩 옮기기
코드
// BOJ - 1514 : 자물쇠
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
const int INF = 987654321;
int n, a[104], b[104], dp[104][10][10][10][2];
int _mod(int x)
{
return (x < 0) ? x + 10 : x % 10;
}
int f(int pos, int x, int y, int z, int flag)
{
if (pos == n) return 0;
int& res = dp[pos][x][y][z][flag];
if (res != -1) return res;
if (_mod(x + a[pos]) == _mod(b[pos])) return res = min(f(pos + 1, y, z, 0, 0), f(pos + 1, y, z, 0, 1));
res = INF;
int _flag = flag ? 1 : -1;
for (int i = 1; i <= 3; i++)
{
res = min(res, 1 + f(pos, _mod(x + i * _flag), y, z, flag));
res = min(res, 1 + f(pos, _mod(x + i * _flag), _mod(y + i * _flag), z, flag));
res = min(res, 1 + f(pos, _mod(x + i * _flag), _mod(y + i * _flag), _mod(z + i * _flag), flag));
}
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
memset(dp, -1, sizeof(dp));
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%1d", &a[i]);
for (int i = 0; i < n; i++) scanf("%1d", &b[i]);
cout << min(f(0, 0, 0, 0, 0), f(0, 0, 0, 0, 1)) << '\n';
return 0;
}
평가
- dp의 상태값을 잘 설정하는 것이 중요
- 경우의수 18가지를 모두 잘 체크할 수 있게 로직을 짜야 한다
- 체크를 진행할 때, 인덱스 기준으로 하나 씩만 맞게 체크해도 충분하다
