프로그래머스 마법의 엘리베이터

문제

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

프로그래머스

 

풀이

단순히 각 자릿수의 합은 반례가 생긴다.

ex) test case 999의 답은 9*3=27이 이니라 1을 더해 1000으로 만들고 1000을 뺴주면되므로 2이다.

어떤 테스트케이스에 대해 일부 자리들을 선택해 다음 연산들을 수행하고 각 자릿수의 합을 계산해야한다: 선택한 자리의 수가 x라면 10-x를 해당자리에 더해준다.

이것을 자리를 올려준다고 표현한다.

 

솔직히 어디서 더해줘야하는지 모르겠다.

그래서 브루트포싱을 했다.

최대 input이 8자리이므로 8bit에대해 i(0<=i<8)번째 bit가 1이면 자리를 올려주고 0이라면 그대로 가져간다.

1 << 8 = 256이므로 8bit로 표현가능한 모든 bit에 대해 돌려도 시간초과가 나지 않는다.

 

def solution(S):
    ans = [0] * (1 << 8) # 각 비트별 결과값을 담음
    def getCurrent(idx,num): # 숫지num에 대해 idx번째 자릿수를 가져옴
        R = num % (10 ** (idx + 1))
        return R // (10 ** idx)
    for i in range(1 << 8):
        s = S 
        tmp = 0 # bit i에 대한 결과
        for j in range(9): # 8자리에서 올려주면 수가 9자리까지 되므로
            if (1 << j) & i: # 올려주기
                x = getCurrent(j,s) 
                tmp += 10 - x
                s += (10 - x) * (10 ** j)
        for j in range(9): # 결과 계산
            tmp += getCurrent(j,s)
        ans[i] = tmp
    return min(ans)