[BOJ] 13392 방법을 출력하지 않는 숫자 맞추기

문제

13392번: 방법을 출력하지 않는 숫자 맞추기

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

https://www.acmicpc.net/problem/13392

풀이

코드

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
int n;
string s, e;
int dp[10000][10];
 
int go(int ix, int cnt) {
    if (ix == n) return 0;
    if (dp[ix][cnt] != -1) return dp[ix][cnt];
 
    // 오른쪽 회전
    int st = int(s[ix] - '0') + cnt, fi = int(e[ix] - '0'), tmp = 0, ret;
    st %= 10;
    if (fi > st) tmp = st + 10 - fi;
    else if (fi < st) tmp = st - fi;
    ret = go(ix + 1, cnt) + tmp;
 
    // 왼쪽 회전
    st = int(s[ix] - '0') + cnt, fi = int(e[ix] - '0'), tmp = 0;
    st %= 10;
    if (fi > st) tmp = fi - st;
    else if (fi < st) tmp = 10 - st + fi;
    ret = min(ret, go(ix + 1, (cnt + tmp)%10) + tmp);
 
    return dp[ix][cnt] = ret;
}
 
int main() {
    memset(dp, -1, sizeof(dp));
 
    scanf("%d", &n);
    cin >> s >> e;
    printf("%d", go(0, 0));
}