[BOJ/백준] 1463 1로 만들기

a= int(input())
def cal(a):
    temp = []
    for i in a:
        temp.append(i-1)
        if i%3==0:
            temp.append(i/3)
        if i%2==0:
            temp.append(i/2)
    return temp
cnt=0
minimum=[a]
while True:
    if a==1:
        print(cnt)
        break
    temp=minimum[:]
    minimum=[]
    minimum=cal(temp)
    cnt+=1
    if min(minimum)==1:
        print(cnt)
        break

유명한 DP 문제이다.

각각의 연산을 한뒤에 새롭게 옮겨가는 LIST를 따로 만들어주고, 그걸 갱신하면서 횟수가 어느회차인지 알면된다.

 

N = int(input())
number_list = [N]
cnt = 0
flag = False
if N == 1:
    print(0)
else:
    while True:
        new_number = []
        for numbers in number_list:
            if numbers == 1:
                flag = True
                break

            if not numbers%3:
                new_number.append(numbers/3)
            if not numbers%2:
                new_number.append(numbers/2)
            new_number.append(numbers-1)
        if flag:
            print(cnt)
            break
        cnt += 1
        number_list = new_number[:]

똑같은데 이런식으로도 만들수 있다.