[DP] 백준 #1463: 1로 만들기

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다.
    - X가 3으로 나누어 떨어지면, 3으로 나눈다. 
    - X가 2로 나누어 떨어지면, 2로 나눈다.
    - 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.
연산을 사용하는 횟수의 최솟값을 출력하시오.

 

 

 

위의 규칙에 따라 1~10까지의 수를 계산해보면 다음과 같다.

연산	1	2	3	4	5	6	7	8	9	10
최소값	0	1	1	2	3	2	3	3	2	3
+ 1	0	1	2	2	3	4	3	4	4	3
/ 2	0	1	-	2	-	2	-	3	-	4
/ 3	0	-	1	-	-	2	-	-	2	-

 

입력된 수가 2로 나누어 떨어지거나 3으로 나누어 떨어질 경우
2로 나누거나 3으로 나누는게 최소 횟수이다.
나누어 떨어지지 않는 경우,
바로 앞의 수의 최소횟수에 1을 더해서 계산이 가능하다.

 

따라서,
1) 나누어 떨어지지 않을 경우

dp = [0] * (n + 1)
dp[i] = dp[i - 1] + 1

2) 2의 배수일 경우

dp[i] = dp[i // 2] + 1

3) 3의 배수일 경우

dp[i] = dp[i // 3] + 1

이 세 가지 경우의 최소값이 결과가 될 것이다.

 

따라서

n = int(input())

dp = [0] * (n + 1) 
# dp[1] = 0인 초기값 설정

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

 

Dynamic Programming이 이제 뭔지 조~금 알것같다