백준 1463번 : 1로 만들기 (Python)

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

n = int(input())
sols = [0] * (n+1)

for i in range(2, n+1) :
    # 1 빼기
    sols[i] = sols[i-1] + 1
    # 2로 나눌 수 있으면 i//2 비교
    if i % 2 == 0 :
        sols[i] = min(sols[i//2] + 1, sols[i])
    # 3으로 나눌 수 있으면 i//3 비교
    if i % 3 == 0 :
        sols[i] = min(sols[i//3] + 1, sols[i])

print(sols[-1])

이 문제는 1부터 시작해서 1을 더하거나, 2를 곱하거나, 3을 곱해서 n까지 최소 회수로 도달하는 문제와 완전히 동일하다.

주어진 n에 대해 답을 구하는 함수를 $f(n)$이라고 정의하면, $f(n)$은 다음과 같이 구할 수 있다.

1. $f(n-1) + 1$
2. n이 2의 배수라면 $f(n/2) +1$
3. n이 3의 배수라면 $f(n/3)+1$

1, 2, 3 중 최소값이 $f(n)$이 된다.

 

먼저 길이가 n+1인 리스트 sols를 생성하고 모든 값을 0으로 초기화한다.

sols[i]는 f(i)의 값이라고 이애하면 된다.

1에서 1이 되려면 연산을 0회 수행(아무것도 하지 않아도 됨)하면 되므로 sols[1] = 0 이다.

다음 sols[2]부터, 1, 2, 3의 조건을 비교해 최소값을 넣어준다.