[Algo] 백준 1463번 ‘1로 만들기’ (python)

[Silver III] 1로 만들기 - 1463

문제 링크

성능 요약

메모리: 39504 KB, 시간: 552 ms

분류

다이나믹 프로그래밍

문제 설명

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 10⁶보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

코드

import sys

n = int(sys.stdin.readline())

dp = [0, 0, 1, 1]

for i in range(4, n+1):
    if i % 2 == 0 and i % 3 == 0:
        min_value = min(dp[i-1], dp[i//2], dp[i//3])
    elif i % 2 == 0:
        min_value = min(dp[i-1], dp[i//2])
    elif i % 3 == 0:
        min_value = min(dp[i-1], dp[i//3])
    else:
        min_value = dp[i-1]
    dp.append(min_value + 1)

print(dp[n])

코드 리뷰

이 문제는 DP의 가장 기초라고 볼 수 있는 문제이다. DP를 접하고 거의 초반부에 푼 코드라 다른 코드들에 비해 조금 엉성할 수 있지만, 이 문제를 푼 후 다른 코드들과 비교해 봤을 때 이 코드가 그래도 조금 더 이해가 쉽고 직관적이라는 생각이 든다. 먼저 dp리스트에는 n번째 정수의 1로 만들기 위한 최소 연산 횟수가 들어간다. dp = [0, 0, 1, 1]로 초기화 해준 이유는 그냥 index번호 0과 1은 쓰지 않을 예정인데 비워두면 연산 과정에서 한 번 더 생각해야 할 것 같아서 그냥 0으로 초기화 해둔것이다. 그 후 for문을 돌리면서 dp리스트의 값들을 채워주는데, 2로도 나누어 떨어지고 3으로도 나누어 떨어진다면 min_value = min(dp[i-1], dp[i//2], dp[i//3])를 사용해 가능한 모든 경우의 수를 생각해봤고, 2로만 나누어 떨어지거나 3으로만 나누어 떨어진다면 min_value = min(dp[i-1], dp[i//2])과 min_value = min(dp[i-1], dp[i//3])으로 각각 min_value를 초기화 해주었다. for문을 탈출하면 dp.append(min_value + 1)로 최종적으로 dp리스트에 저장해주는데, 여기서 1을 더하는 이유는 i-1, i/2, i/3의 숫자를 만드는 데 1의 연산이 필요하기 때문이다.