[백준] 1463_1로 만들기 (dp 이용)

📕 문제

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

1463번: 1로 만들기

 

💡 풀이법

1. dp라는 리스트를 만들어준다. 이 리스트에는 1에서 해당 인덱스의 숫자가 될때까지의 최소한의 연산이 들어간다.

2. 나는 반대로 1에서 정수 N까지 가는 연산을 구해줬다.

3. 처음에는 +1 연산으로만 간다고 생각하고 숫자를 dp에 숫자를 넣어준다.

4. 더하기 1 연산은 모든 경우에 다 가능하기 때문에 dp[현재 인덱스 -1] + 1 의 값과  현재 인덱스의 값을 비교해서 더 작은 걸 dp에 넣는다.

5. 이제 for문을 돌며 현재 인덱스가 3의 배수이면 곱하기 3 연산을 쓸 수 있는 것이므로 dp[현재 인덱스//3] + 1 의 값과 현재 인덱스의 값을 비교해서 더 작은걸 dp에 넣는다.

6. 현재 인덱스가 2의 배수이면 곱하기 2 연산을 쓸 수 있는 것이므로 dp[현재 인덱스//2] + 1 의 값과 현재 인덱스의 값을 비교해서 더 작은걸 dp에 넣는다.

 

X = int(input())
dp = [0] + [i for i in range(X+1)]

for n in range(1, X+1):
    dp[n] = min(dp[n], dp[n-1]+1)
    if not n % 3:
        dp[n] = min(dp[n], dp[n//3]+1)
    if not n % 2:
        dp[n] = min(dp[n], dp[n//2]+1)

print(dp[X])