[KOI] 백준 2494 - 숫자 맞추기

www.acmicpc.net/problem/2494

 

동적계획법을 통해 현재 자물쇠의 상태를 저장하여 푸는 문제이다.

 

나사가 몇번 회전했는지도 구해야 하므로 dp 테이블 뿐만 아니라 역추적 테이블도 생성해야 한다.

 

각 테이블의 정의는 다음과 같다.

 

dp 테이블

dp[i][j] := i번째 나사가 현재 상태에서 j번 왼쪽으로 회전한 상태일 때 원하는 숫자로 맞추기 위해 회전한 칸수의 최소

 

역추적 테이블

backward[i][j] := i번째 나사가 왼쪽으로 j번 회전한 상태일 때 최적해에 도달하기 위해 왼쪽으로 회전한 칸수

 

바텀 업 dp로 현재 나사에서 원하는 상태를 오른쪽으로 돌려서 맞췄을 때, 왼쪽으로 돌려서 맞췄을 때를 계산해준다. 회전 칸수는 모듈러 연산을 이용해 구해준다.

 

이 과정에서 최적해가 갱신된다면 회전한 칸수 j를 backward에 저장해준다.

 

이렇게 동적계획법을 수행하고나면 최적해는 n번째 나사에서 0 ~ 9칸 왼쪽으로 회전한 상태 중 최소값이 된다.

 

어떻게 회전했는지 알기 위해 최적해가 될 때 j를 가지고 다시 뒤에서부터 역추적을 해보자.

 

우리는 각 나사가 최적해에 도달하기 위해 왼쪽으로 회전한 칸수를 backward에 저장했다.

 

backward[i][j] = j면 i번째 나사가 최적해로 도달하기 위해 오른쪽으로 나사를 돌렸다는 뜻이고 그렇지 않으면 왼쪽으로 나사를 돌렸다는 뜻이 되기 때문에 방향성을 판별할 수 있다.

 

오른쪽으로 나사를 돌린 경우 출력값은 -(dp[i][j] - dp[i - 1][j])가 된다.

 

왼쪽으로 나사를 돌린 경우 출력값은 dp[i][j] - dp[i - 1][이전 나사에서 왼쪽으로 회전한 칸수]가 된다.

 

이 출력값을 배열에 저장해주고 형식에 맞게 출력하면 된다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
int start[10001], goal[10001];
int dp[10001][10];
int backward[10001][10];
int reconstruct[10001];
 
inline int circular(int x)
{
    while (x < 0)
        x += 10;
    return x % 10;
}
 
int main()
{
    fill(&dp[0][0], &dp[0][0] + 10001 * 10, 1e9);
    cin.tie(0); ios::sync_with_stdio(false);
 
    cin >> n;
    cin.get();
 
    for (int i = 1; i <= n; ++i)
        start[i] = cin.get() - '0';
    cin.get();
    for (int j = 1; j <= n; ++j)
        goal[j] = cin.get() - '0';
    
    for (int i = 0;  i < 10; ++i)
        dp[0][i] = i;
    
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            int left = circular(goal[i] - start[i] - j);
            int right = circular(-left);
 
            if (dp[i][j] > dp[i - 1][j] + right)
            {
                dp[i][j] = dp[i - 1][j] + right;
                backward[i][j] = j;
            }
 
            if (dp[i][circular(j + left)] > dp[i - 1][j] + left)
            {
                dp[i][circular(j + left)] = dp[i - 1][j] + left;
                backward[i][circular(j + left)] = j;
            }
        }
    }
 
    int res = 1e9, minshft;
 
    for (int i = 0; i < 10; ++i)
        if (res > dp[n][i])
            res = dp[n][i], minshft = i;
    cout << res << '\n';
 
    int idx = n;
    while (idx)
    {
        if (backward[idx][minshft] == minshft)
            reconstruct[idx] = -(dp[idx][minshft] - dp[idx - 1][minshft]);
        else
            reconstruct[idx] = dp[idx][minshft] - dp[idx - 1][backward[idx][minshft]];
        minshft = backward[idx--][minshft];
    }
 
    for (int i = 1; i <= n; ++i)
        if (reconstruct[i])
            cout << i << " " << reconstruct[i] << '\n';
}