백준 1463 - 1로 만들기( Python )

https://www.acmicpc.net/problem/1463

 

전형적인 dp유형의 문제로 입력값이 1000000개, 백만개로로 적은편이기때문에 더욱이 dp로 풀어야하는 문제임을 알 수 있다.

점화식을 찾아보자

array[1] = 0
array[2] = min(array[1] + 1, array[2//2] + 1)
array[3] = min(array[2] + 1, array[3//3] + 1)
array[4] = min(array[3] + 1, array[4//2] + 1)
array[5] = array[4] + 1 //2와 3으로 나누어 지지 않는 경우
array[6] = min(array[5] + 1, array[6//3] + array[3])
array[7] = array[6] + 1
array[8] = min(array[7] + 1, array[8//2] + 1)
array[9] = min(array[8] + 1, array[9//3] + 1)
array[10]= min(array[9] + 1, array[10//2] + 1)

 

멋지게 한줄로 적진 못하겠지만 계속 규칙적인 식이 나온다는 것을 알 수 있다.

 

n = int(input())

array = [0] * 1000001 #입력값의 개수만큼 배열 생성 n+1개로 생성해도 무관

for i in range(2, n + 1):
    array[i] = array[i-1] + 1 #2와 3으로 나누어지지 않는 경우
    if i % 2 == 0:
        array[i] = min(array[i], array[i//2] + 1)
    if i % 3 == 0: # 2와 3의 공배수가 있기 때문에 elif를 사용하면 안됨
        array[i] = min(array[i], array[i//3] + 1)
print(array[n])