문제

점프와 순간 이동

총 풀이시간 : 40분

한 번에 K 칸을 앞으로 점프하거나, (현재까지의 거리)*2로 순간이동할 수 있다. K만큼 전진시엔 K만큼의 건전지를 사용하므로, 순간이동이 더 효율적이다. N까지 갈 때, 건전지 사용량의 최솟값을 구하라.

첫 시도 (실패)

값은 매번 고정되고, 직전의 위치로 항상 효율적인 답을 얻을 수 있으므로 DP를 사용했다.

DP[0] = 0

DP[1] = 1

DP[2] = DP[1]*2 = 1

DP[3] = DP[2]+1 = 2

(3은 2로 나누어지지 않으므로 무조건 전 칸에서 직진)

DP[4] = min(DP[3]+1, DP[2]) = min(3,1) = 1

DP[5] = DP[4]+1 = 2

DP[6] = min(DP[5]+1, DP[3]) = min(3,2) = 2

근데 N의 최대값이 10억(10^9)이므로, 파이썬의 배열 사이즈 제한을 넘을 것 같아서 N이 홀수일 경우 최대한 줄여주기로 했다.

DP[5000] = DP[2500] = DP[1250] = DP[625] 이므로 순간이동만으로 후진했을 때 도달할 수 있는 가장 작은 값까지 DP 배열을 생성한다. 즉 해당 값이 최종 도착점이 된다.

def getFinalLocation(n) :
    while(n%2 == 0) :
        n /= 2
    return int(n)

def makeDP(FinalLocation) :
    DP = [0]*(FinalLocation+1)
    DP[0] = 0
    DP[1] = 1
    for i in range(2, FinalLocation+1) :
        DP[i] = DP[i-1]+1
        if(i%2==0) : DP[i] = min(DP[i],DP[int(i/2)])
    return DP[FinalLocation]        

def solution(n):
    return makeDP(getFinalLocation(n))

1차시도 채점 결과 정확성: 60.0/60.0 효율성: 4.0/40.0 합계: 64.0 / 100.0

두번째 시도 (성공)

효율성 테스트에서 시간초과뿐만이 아니라 런타임에러를 받았다. 이건 분명히 배열 크기때문이라는 생각에, 머리를 싸매다가 백트래킹으로 다시 접근했다.

def getFinalLocation(n) :
    while(n%2 == 0) :
        n /= 2
    return int(n) 

def Backtracking(FinalLocation) :
    ans = 0
    while(FinalLocation != 0) :
        if(FinalLocation%2 == 0): 
            FinalLocation /= 2
        else :
            FinalLocation -= 1
            ans += 1
    return ans

def solution(n):
    return Backtracking(getFinalLocation(n))

허무하게도 백트래킹이 정답이었다. 백트래킹 문제를 많이 안풀어본 터라, 곧바로 백트래킹으로 접근하지못한게 많이 아쉽다.