백준 2494 (C++) 숫자 맞추기

최초 업로드: 2025-04-30 08:39:40

최근 수정 시간: 2025-07-25 09:19:23

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] 숫자 맞추기

[문제 링크](https://www.acmicpc.net/problem/2494)

## 문제 설명

아래 그림과 같이 N개의 회전이 가능한 숫자 나사가 아래위로 연결되어 있다. 가장 위에 있는 숫자나사는 숫자나사 1이고 가장 아래에 있는 숫자나사는 숫자나사 N이다. 모든 숫자나사는 각각 10개의 면을 가지고 있고, 각 면에는 오른쪽 방향으로 0, 1, 2, 3, …, 9까지의 숫자가 하나씩 순서대로 적혀 있다. 하나의 숫자나사를 왼쪽으로 회전 시키면, 이 나사보다 아래에 위치한 모든 나사는 같이 따라서 돌게 되지만, 나사를 오른쪽으로 회전시키면, 다른 나사는 함께 돌지는 않는다. 정면에서 보아 위에서부터 아래쪽으로 숫자를 읽어 내려간다고 할 때, 현재의 상태에서 가장 적은 칸수의 움직임으로 원하는 숫자를 만들기 위한 방법을 출력하는 프로그램을 작성하라.

예를 들어 세 개의 숫자나사가 주어졌을 때, 정면에서 보는 현재 상태가 326이고 원하는 상태는 446이라면 최소 회전 칸수는 4이다. 먼저 숫자나사 1을 왼쪽으로 한 칸 돌리면 437이 되고, 숫자나사 2를 역시 왼쪽으로 한 칸 돌리면 448이 되며, 마지막으로 숫자나사 3을 오른쪽으로 두 칸 돌리면 446이 된다.

## 입력

첫째 줄에는 숫자나사의 개수 N이 주어지고, 둘째 줄에는 현재의 상태가, 셋째 줄에는 원하는 상태가 주어진다. N은 3 이상이고 10,000 이하이다.

## 출력

첫째 줄에는 현재 상태에서 원하는 상태로 도달하는데 필요한 최소 회전 칸수를 출력한다. 다음 줄부터는 회전 순서대로 각 줄에 하나의 숫자나사 번호와 회전 칸수를 빈칸을 사이에 두고 출력한다. 회전 칸수는 왼쪽을 기준으로 하여 출력한다. 만일 왼쪽으로 4칸 회전한다면 4를, 오른쪽으로 3칸 회전한다면 -3을 출력한다. 답이 여러 개이면 그 중에 하나만 출력한다.

## 풀이
#### dp[i][j]를 i번째 숫자 나사까지 왼쪽으로 j%10번 돌렸을 때의 최소 회전 칸수로 두고 풀었다. prv 배열로 직접 도착 지점에서 출발 지점까지 역추적하여 출력해주었다. prv[i][j]에 i번째 숫자 나사에 도달하기 위해 직전에 왼쪽 혹은 오른쪽으로 이동한 거리를 담았다.(오른쪽 이동을 -dis, 왼쪽 이동을 dis)

``` c++
#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

/** 
 * dp[i][j] : i번째 숫자 나사까지 왼쪽으로 j번 돌렸을 때의 최소 회전 칸수
 * prv[i][j] : 이동
 */
int dp[10001][10], prv[10001][10];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; string a, b; cin >> n >> a >> b;

fill(&dp[0][0], &dp[10000][10], INF);
 dp[0][0]=0;
 for(int i=0;i<n;i++) {
 for(int j=0;j<10;j++) {
 // 오른쪽으로 돌리기(a[i]가 작아짐)
 int moveR = ((a[i]-'0'+j)%10 + (10-(b[i]-'0')))%10;
 if(dp[i+1][j] > dp[i][j] + moveR) {
 dp[i+1][j] = dp[i][j] + moveR;
 prv[i+1][j] = -moveR;
 }

// 왼쪽으로 돌리기(a[i]가 커짐)
            int moveL = ((b[i]-'0') + (10-(a[i]-'0'+j)%10))%10; 
            if(dp[i+1][(j+moveL)%10] > dp[i][j] + moveL) {
                dp[i+1][(j+moveL)%10] = dp[i][j] + moveL;
                prv[i+1][(j+moveL)%10] = moveL;
            }
        }
    }

int minCost=INF, idx=0;
 for(int i=0;i<10;i++) {
 if(minCost > dp[n][i]) {
 minCost = dp[n][i];
 idx = i;
 }
 }

vector<pair<int, int>> res;
 for(int depth=n;depth>=1;depth--) {
 res.push_back({depth, prv[depth][idx]});
 if(prv[depth][idx]>0) idx = (idx-prv[depth][idx]+10)%10;
 }

cout << minCost << '\n';
 for(int i=n-1;i>=0;i--) {
 cout << res[i].first << ' ' << res[i].second << '\n';
 }
}
```