1463번

문제

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

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

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

입력

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

출력

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

문제 바로가기

백준 1463번

---

✏️분석 및 풀이 - dp (Dynamic Programming)

전의 결과를 다음 결과에 이용하게 되는 점화식을 이용하는 dp문제

x = 10
10 -> 5 -> 4 -> 2 -> 1 : 4번
10 -> 9 -> 3 -> 1 : 3번

이와 같이, 어떤 식을 먼저 이용하느냐에 따라 수식을 이용하는 횟수가 달라진다. 이 중에서도 값이 가장 적은 것을 출력해야한다.
또한, x값이 10일 때는, 10-> 9-> 3-> 1 처럼 앞에서 구한 결과값을 저장하였다가 후에 사용한다.

✔️dp 확인

배열 dp에는 n을 1로 만드는 최소연산 횟수 값이 저장된다.
1부터 7까지 dp에 저장되는 과정 및 값을 확인하면 어떤식인지 감이 올것이다.

1. dp[1] = 0

2. dp[2] = 1
	- 2/2 = 1
    
3. dp[3] = 1
	- 3/3 = 1
    
4. dp[4] = 2
	- 4/2 = 2
    - 2/2 = 1
    
5. dp[5] = 3
	- 5-1 = 4
    - 4/2 = 2
    - 2/2 = 1 
    
6. dp[6] = 2
	- 6/3 = 2	
    - 6/2 = 1 
    
7. dp[7] = 3
	- 7-1 = 6
    - 6/3 = 2
    - 6/2 = 1

5, 6, 7의 값을 보면 앞의 값의 과정을 거친다는 것을 확인할 수 있다. 즉, dp[5]는 1+dp[4]값이므로 3이다.dp[6]은 1+dp[6//3] 또는 1+dp[6//2]값으로 2이다. dp[7]은 1+dp[6]으로 3이 된다.

✔️정리

이러한 규칙을 바탕으로 정리해보자.
1. dp[n]의 값은 구할 수 있는 값중 최소값이어야 한다.
2. dp[1] = 0, dp[2] = 1, dp[3] = 1
3. n>1이고, n이 2 또는 3으로 나눠지는 경우
- dp[n] = 1+dp[n//2] or 1+dp[n//3]
- dp[n] = 1+dp[n-1]
4. n>1이고, n이 2 또는 3으로 안 나눠지는 경우
- dp[n] = 1+dp[n-1]

---

💡풀이 코드

n = int(input())

dp = [0] * (n+1)

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])