문제 풀이 아이디어

점프와 순간이동과 유사한 문제입니다. 수를 바꾸는 몇가지 선택지를 가지고 원하는 숫자까지 도달하는 문제입니다.

완전 탐색?

이 문제의 N은 최대 100,000,000입니다. 버튼의 종류는 최대 16종류가 되겠습니다. 따라서 완전 탐색을 하게 되면 무조건 시간초과입니다.

규칙

마법의 돌을 최대한 절약하기 위해서는 버튼을 누르는 횟수를 최대한 줄여야 합니다. 다시 말하면 “+”, “-”에 관계 없이 큰 숫자를 눌러야 합니다.

작은 숫자 0으로 만들기

“-10” 버튼을 눌러서 0층으로 가기 위해서는 1의 자리 숫자가 있으면 안됩니다. 마찬가지로 “-100”의 버튼을 눌러서 0층으로 가기 위해서는 10이 자리 숫자가 있으면 안됩니다.

따라서 숫자가 큰 버튼을 쓰기 위해서는 그 숫자보다 자릿수가 낮은 숫자들은 모두 0이어야 합니다. 이 문제는 1의 자리 숫자부터 작은 버튼을 최대한 적게 사용해서 0으로 만들고 큰 숫자의 버튼을 이용해서 0층으로 가는 문제입니다.

자세한 과정은 코드에 기록해두도록 하겠습니다.

코드

func solution(_ storey:Int) -> Int {
    
    var storey = storey
    var ans = 0
    
    // 0층에 도착할 때까지 반복
    while storey != 0 {
        
        // 1의 자리수
        let now = storey % 10
        // 10의 자리수
        let next = (storey / 10) % 10
        
        // 1의 자리 수가 5보다 크면 더해서 올림
        if now > 5 {
            ans += 10 - now
            storey += 10
        // 1의 자리 수가 5보다 작으면 빼서 내림
        } else if now < 5 {
            ans += now
        // 1의 자리 수가 5면 다음 자릿수가 5 이상이면 올리고 아니면 내림
        } else {
            ans += 5
            storey += next >= 5 ? 10 : 0
        }
        
        // 마지막 자리 수는 0이 되었으므로 (= 버튼을 누를 필요 없으므로) 제거
        storey /= 10
    }

    return ans
}