12852. 1로 만들기2

문제 링크

12852. 1로 만들기2

문제 코드

N = int(input())

num_list = [0]*(N+1)
before_list = [0]*(N+1)

for i in range(1,N+1):
    divide_two = float('INF')
    divide_three = float('INF')
    if i == 1:
        num_list[i] = 0
        before_list[i]= 1
        continue

    if i%2 == 0:
        divide_two = num_list[i//2] +1

    if i%3 == 0:
        divide_three = num_list[i//3]+1

    num_list[i] = min(num_list[i-1]+1, divide_two, divide_three)

    if num_list[i-1] + 1 == min(num_list[i-1]+1, divide_two, divide_three):
        before_list[i] = i-1
    elif divide_two == min(num_list[i-1]+1, divide_two, divide_three):
        before_list[i] = i//2
    else :
        before_list[i] = i//3

print(num_list[N])

idx = N
result_string = str(N)
while idx > 1:
    result_string += " "+ str(before_list[idx])
    idx = before_list[idx]

print(result_string)

문제 풀이

• a[i] = max(a[i-1]+1 , a[i//2]+1 , a[i//3]+1) 이라는 간단한 점화식으로 풀수 있는 문제
• 숫자가 지나간 루트를 기록할 필요가 있으므로 before list를 만들어서 가장 min일때의 바로 앞 경로를 저장하도록 함