12. 마법의 엘리베이터

https://school.programmers.co.kr/learn/courses/30/lessons/148653

각 자리수마다 수를 올릴지 내릴지 2가지 케이스가 총 9가지 이므로 2^9로 해결할 수 있는 문제이다. 직관적으로 일의 자리 수부터 올리거나 내리거나 하는 작업을 한 후에 다음 자리 수를 처리하는게 최적임을 알 수 있다. 예를 들어 십의 자리 수를 먼저 처리하고 일의 자리 수를 처리하면 십의 자리수가 0인 상태에서 일의 자리 수에 의해 다시 십의 자리수가 1이 될 수 있기 때문이다.

#include <bits/stdc++.h>
using namespace std;
int ans = 1e9;

void dfs(int n, int cnt)
{
    if (n == 0)
    {
        ans = min(ans, cnt);
        return;
    } 
    
    int r1 = 10 - (n % 10);
    if (n > 1) dfs(n / 10 + 1, cnt + r1);
    int r2 = n % 10;
    dfs(n / 10, cnt + r2);
}

int solution(int n) 
{
    dfs(n, 0);
    return ans;
}