[동적 계획법] 1로 만들기

다른 사람들의 풀이를 보니, 메모이제이션으로 쉽게 풀 수 있는걸 너무 복잡하게 생각한 것 같다.

 

1463번: 1로 만들기

 

from sys import stdin

N = int(stdin.readline())

m = {1: 0}


def check(no):
    global m
    if no <= N and no not in m:
        m[no] = 0
        return True
    return False


pre = [1]
count = 0
while True:
    if N == 1:
        break

    pre_new = []
    count += 1
    for i in pre:
        if check(i * 2):
            pre_new.append(i * 2)
        if check(i * 3):
            pre_new.append(i * 3)
        if check(i + 1):
            pre_new.append(i + 1)

    pre = pre_new

    if N in m:
        break

print(count)