문제
총 풀이시간 : 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))
허무하게도 백트래킹이 정답이었다. 백트래킹 문제를 많이 안풀어본 터라, 곧바로 백트래킹으로 접근하지못한게 많이 아쉽다.