백준 1514 - 자물쇠

www.acmicpc.net/problem/1514

 

기본 풀이는 dp이면서도 점화식 진행에 탐욕적 방법이 들어가는 어려운 문제이다.

다음 상태로의 진행

자물쇠의 왼쪽 디스크부터 오른쪽 방향으로 진행해 잠금을 푼다고 해보자.

 

그렇다면 첫 시작할 때 기준점은 0번 디스크이고 기준점에서 2번 디스크까지 고려를 해야 한다.

 

다음 기준점인 1번 디스크로 가기 위해선 0번 디스크가 무조건 알맞은 숫자에 맞춰져 있어야 하고 이는 탐욕적 속성을 만족해야 함을 알 수 있다.

 

그렇다면 다음 상태는 우선 기준 디스크가 맞춰진 상태에서 오른쪽으로 인접한 두 개의 디스크를 어떻게 회전시킬 것이냐에 따라 갈리게 된다.

 

기준 디스크를 x, 첫번째 인접 디스크를 y, 두번째 인접 디스크를 z라고 하고 설명하겠다.

 

1. x와 y, z를 같이 회전시키는 경우

 

디스크는 최대 연속된 3개를 3칸 회전시킬 수 있으므로 x와 y, z들도 회전시키는 경우를 고려해야 한다.

 

또한 기준 디스크는 같이 회전한 것 외에도 추가적으로 혼자 회전하는 것도 가능함을 인지해야 한다.

 

2. x와 y, z를 별개로 회전시키는 경우

 

이 경우는 x가 되는 기준점이 오른쪽으로 옮기면서 고려가 되므로 신경쓰지 않아도 된다.

 

x는 이미 올바르게 맞춘다고 강제한 상태이므로 나머지 y, z를 회전하는 경우를 고려해서 동적계획법을 전개하면 될 것이다.

 

물론 돌리는 방향도 두가지가 되기 때문에 시계/반시계 방향으로 회전시키는 경우도 각각 생각한다.

회전 횟수 계산

아까도 언급했듯이 디스크 숫자 a를 b로 맞출 때 시계/반시계 방향으로 회전하여 맞출 수 있다. 이 두 경우를 따로 계산해야 한다.

 

우선 x가 알맞은 숫자로 맞춰지기 위해 시계/반시계 방향으로 회전했을 때 이동한 칸 수를 계산해준다.

 

나머지 y와 z는 아까 언급한 디스크를 회전하는 경우 중 1번을 생각해보자.

 

y는 x보다 더 많이 회전시키지 않는다. (더 시킨다면 그 경우는 1번이 아니라 2번이 될 것이다.)

 

z는 첫번째 y보다 더 많이 회전시키지 않는다. (아까와 마찬가지)

 

그렇다면 y는 x와 같이 회전하는 길이만큼 중복이 생길 것이고 z도 y와 같이 회전하는 길이만큼 중복이 생길 것임을 알 수 있다.

 

중복을 제외하고 각 디스크가 따로 이동한 칸의 횟수를 구하는 계산을 다음과 같이 하면 된다.

 

x만 따로 이동한 칸 수 = x를 맞추기 위해 이동한 칸 수 - y가 이동된 칸 수

 

y만 따로 이동한 칸 수 = y가 이동된 칸 수 - z가 이동된 칸 수

 

z만 따로 이동한 칸 수는 z가 이동된 칸 수 그대로이다.

 

이 세 결과에 대해 몇번 회전한 건지 계산하여 더하면 총 회전 횟수가 나오게 되고 이 중에서 최솟값을 찾으면 문제를 풀 수 있다.

구현

탑 다운 dp로 구현했으며 dp 테이블을 다음과 같이 정의한다.

 

dp[i][j][k][s] := i번째 디스크가 기준이고 i번째 디스크의 숫자가 j, i + 1번째 디스크의 숫자가 k, i + 2번째 디스크의 숫자가 s이기 위한 최소 회전 횟수

 

또한 기준점을 이동하는 과정에서 인접 디스크의 범위가 자물쇠의 전체 디스크를 넘을 수 있다.

 

인접 디스크의 번호가 전체 디스크의 크기를 넘어 생기는 오연산을 방지하기 위해 dp 테이블과 자물쇠 배열의 길이를 조금 더 길게 잡는다. 그렇게 되면 전역변수로 초기화 된 배열은 0으로 초기화 되므로 원래 자물쇠에 0을 몇개 더 붙인 모양이 되어 예외를 고려하지 않아도 된다.

 

인접 디스크가 이동하는 경우는 이중 루프를 사용했다.

 

z가 이동한 칸 <= y가 이동한 칸 <= x가 이동한 칸 에서 나올 수 있는 조합을 모두 뽑아 최적해를 계산하였다.

 

rot함수를 통해 디스크를 시계/반시계 회전한 결과를 알맞게 처리하고 turn함수로 디스크를 몇번 돌린건지 계산해주었다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
int dp[105][10][10][10];
int start[105], goal[105];
 
inline int rot(int x)
{
    while (x < 0)
        x += 10;
    return x % 10;
}
 
inline int turn(int x)
{
    return x / 3 + (x % 3 != 0);
}
 
int memo(int curr, int a, int b, int c);
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
 
    memset(dp, -1, sizeof dp);
    cin >> n;
    cin.get();
 
    for (int i = 0; i < n; ++i)
        start[i] = cin.get() - '0';
    cin.get();
    for (int j = 0; j < n; ++j)
        goal[j] = cin.get() - '0';
    
    cout << memo(0, start[0], start[1], start[2]);
}
 
int memo(int curr, int a, int b, int c)
{
    if (curr == n)
        return 0;
 
    int &ret = dp[curr][a][b][c];
 
    if (ret != -1)
        return ret;
    
    ret = 1e9;
 
    for (int i = -1; i <= 1; i += 2)
    {
        int mov = rot(rot(goal[curr] - a) * i);
 
        for (int j = 0; j <= mov; ++j)
        {
            for (int k = 0; k <= j; ++k)
            {
                int nb = rot(b + j * i), nc = rot(c + k * i);
                int tmp = memo(curr + 1, nb, nc, start[curr + 3]) + (turn(mov - j) + turn(j - k) + turn(k));
                ret = min(tmp, ret);
            }
        }
    }
 
    return ret;
}