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

1 개요

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

• 백준 온라인 저지 13392번 문제
• BOJ 47단계

2 C++

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

const int MAXN = 10004;
int N;
int arr[MAXN][11];
char curr[MAXN];
char want[MAXN];

int dp(int pos, int offset) {
    if (pos == N) return 0;
    int &result = arr[pos][offset];
    if (result != -1) return result;
    int left = (want[pos] - curr[pos] - offset + 20) % 10;
    int right = 10 - left;
    return result = min(dp(pos + 1, (offset + left) % 10) + left, 
                        dp(pos + 1, offset) + right);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    cin >> curr >> want;
    for (int i = 0; i < N; ++i) {
        curr[i] -= '0';
        want[i] -= '0';
    }
    fill(&arr[0][0], &arr[0][0] + sizeof(arr)/sizeof(arr[0][0]), -1);
    cout << dp(0, 0);
}