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

문제 설명

문제 링크

http://icpc.me/13392

풀이

dp를 이용하여 풀이할 수 있다.

처음에 문제를 보자마자 든 생각은 dp[현재 숫자]로 1차원으로 정의하려 했지만 이렇게 했을 시 dp테이블이 10^10000 크기를 가져야 하므로 바로 패스했다.

그렇다면 현재 숫자를 가벼운 정보를 가지고 구할 수 있어야한다. 현재 내가 보고 있는 i번째 숫자를 알기 위해서 필요한 정보는  0 ~ i-1번째 숫자를  맞추는 동안 왼쪽으로 몇 번을 돌렸는지를 알아야 한다. 그렇기 때문에 dp를 정의할 때 왼쪽으로 돌린 횟수를 가지고 있어야 한다. 또한 왼쪽으로 10번을 돌리면 다시 자기 자신으로 돌아오기 때문에 (왼쪽으로 돌린 횟수) % 10의 정보만 가지고 있으면 된다.

dp[i 번째 숫자 나사를 돌림][0 ~ i -1번째까지 왼쪽으로 돌아간 횟수] = 최솟값으로 dp을 정의할 수 있다.

코드

#include <cstdio>
#include <algorithm>

using namespace std;

int dp[10004][11], n;
char from[10004];
char to[10004];

int dpf(int k, int turn) {
    int &ret = dp[k][turn];
    if (ret) return ret;
    if (k == n) return 0;
    int turnLeft = (to[k] - from[k] - turn + 20) % 10;
    int turnRight = 10 - turnLeft;
    return ret = min(dpf(k + 1, (turn + turnLeft) % 10) + turnLeft, dpf(k + 1, turn) + turnRight);
}

int main() {
    scanf("%d", &n);
    scanf("%s %s", from, to);
    for (int i = 0; i < n; i++) {
        from[i] -= '0';
        to[i] -= '0';
    }
    printf("%d", dpf(0, 0));
}