백준 1463번 - 1로 만들기 [61]

---

문제 유형 :

---

문제

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

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

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

• https://www.acmicpc.net/problem/15829

---

입력

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

출력

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

---

• dp를 사용하는 문제 0,1의 초기값은 정해두고,
• 모든 가능성을 다 구해 그중 작은것을 선택해야한다. (세가지의 연산을 모두 고려해야함)

solution

n = int(input())
dp = [10**6] * (n+1)
dp[0] = 0
dp[1] = 0
def minCount(x):
    #리턴코드
    if dp[x] != 10**6: return  dp[x]
    #모든 가능성을 다 구해 그중 작은것을 선택
    if x %3==0: dp[x] =min(dp[x],minCount(x//3) + 1)
    if x%2 ==0 :
        dp[x] = min(dp[x],  minCount(x//2) + 1)
    dp[x] = min(dp[x], minCount(x-1) + 1)
    # print(x,dp[x])
    return dp[x]
for x in range(2,n+1):
    # print(x,"result = : ",minCount(x))
    minCount(x)
print(dp[n])

나의 한마디

이건 잘 알고있어야 할거같다.

dp문제의 대표