프로그래머스 마법의 엘리베이터 [Lv. 2] (C++)

프로그래머스

1 ~ 100,000,000의 수를 입력 받을 때, -1, +1, -10, +10, -100, +100 등과 같이 절댓값이 10c (c ≥ 0 인 정수) 형태인 정수들을 더하여 0을 만드는 최소 비용을 구해주세요.

 

 

풀이 방법

각 자리수 별로 0으로 만들어 주는 최소 비용을 구해주고 모두 더해주면 됩니다.

ex) 1234를 입력 받은 경우

4 -> +6 or -4
3 -> +7 or -3
2 -> +8 or -2
1 -> +9 or -1

 

자리수별 최소비용을 구한 후 더해주면 모두 해결이 될 것 같지만

한 가지 문제가 발생합니다. +기호를 이용하여 자리수를 0으로 만들어주면 다음 자리수에 영향이 가게됩니다

(1234 에서 +6을 통해 첫 번째 자리를 0으로 만들면 1240으로 다음 계산해야하는 자리수에 영향이 발생)

이 영향이 긍정적일 수도 있고 아닐 수도 있기 때문에 모든 경우를 탐색하여 그중 최소의 경우를 반환해주어야합니다.

 

 

정답 코드

#include<algorithm>

using namespace std;

int GetCost(int num)
{
    if (num < 10)
        return min(num, 10-num+1);
    
    // next = 12345 -> 12340
    int next = num - num % 10;
    
    // + (num % 10) -> 12345를 12340으로 만드는 비용
    int COST_A = GetCost(next / 10) + (num % 10);
    
    // + (10 - num % 10) -> 12345를 12350으로 만드는 비용
    int COST_B = GetCost((next+10) / 10) + (10 - num % 10);

    return min(COST_A, COST_B);
}

int solution(int storey)
{

    return GetCost(storey);
}