백준 16953번: A → B (Python)

간단한 dp문제인 줄 알고 덤볐다가 조금 오래걸렸다. 처음엔 

def dp(que, target, tries):
    nq = []
    if que[0] > target:
        return -1
    for value in que:
        if value * 2 == target or value * 10 + 1 == target:
            return tries+1
        else:
            nq.append(value*2)
            nq.append(value*10 + 1)
    return dp(nq, target, tries+1)
    
a, b = map(int, input().split())
print(dp([a], b, 1))

재귀 함수를 만들어서 돌렸더니 메모리 초과가 났다. 일단 tries 횟수가 높아지면 높아질수록 필요 메모리양이 늘어나고 que[-1]의 메모리엔 높은 수가 들어가기 때문에 자릿수 표현으로 많은 메모리가 추가로 들어간다고 추측된다. 그래서 list를 사용하지 않고 코드를 짜볼려다가 그랬다간 시간이 기하급수적으로 늘어나서 다시 돌아와 코드를 뜯어보았다. 

	#que의 최솟값이 넘어가면 -1
	if not que:
        return -1
        
    if value * 2 < target:
        nq.append(value*2)
    if value * 10 + 1 < target:
        nq.append(value*10 + 1)

그러던 중, 만들 수 없는 경우를 검사하는 코드를 조금만 수정하면 메모리를 크게 줄일 수 있겠다는 생각이 들어서 위의 코드를

def dp(que, target, tries):
    nq = []
    if not que:
        return -1
    for value in que:
        if value * 2 == target or value * 10 + 1 == target:
            return tries + 1
        else:
            if value * 2 < target:
                nq.append(value*2)
            if value * 10 + 1 < target:
                nq.append(value*10 + 1)
    return dp(nq, target, tries + 1)
    
a, b = map(int, input().split())
print(dp([a], b, 1))

이런식으로 바꿨다. 그러니 메모리 문제도 해결되었고 dp로 시간도 줄였다