1로 만들기

출처 : 백준 #1463

시간 제한	메모리 제한
0.15초	128MB

---

문제

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

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

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

---

입력

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

---

출력

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

---

입출력 예시

예제 입력 1

2

예제 출력 1

1

---

예제 입력 2

10

예제 출력 2

3

---

풀이

생각

• 완전 탐색을 해야하는 문제이다.
• 중복되는 경우가 많다.
  • 즉 부분 문제의 해를 계속하여 이용한다.
  • 따라서 DP로 문제를 해결하려 하였다.
• DP에서는 점화식이 가장 중요한데, 이를 생각하는 것이 어려웠다.
• Top down, Bottom up 방식 중 하나를 골라서 풀어야 했는데, Top down 방식이 생각하기는 쉬웠지만 구현이 어려워서 Bottom up 방식을 이용하였다.
• Top down 방식으로 해보니 메모리초과가 나왔다.

풀이 설명

• DP 문제에서 가장 중요한 것은 점화식이다.
  • 이 문제에서의 점화식은 다음과 같다.
  • An = min(An//2, An//3, An-1) + 1
• n이 0일 때와 1일 때는 모두 0이므로 basecase를 작성할 수 있다.
• basecase를 바탕으로 bottom up 방식을 이용하였다.

python code(Top Down)

# 백준 1463번
from sys import stdin
import sys
sys.setrecursionlimit(10**6)
def makeOne(arr, n):
    if n == 1:
        return 0

    if arr[n] > 0:
        return arr[n]   # 이미 채워진 것

    arr[n] = makeOne(arr, n-1) + 1

    if n % 2 == 0:
        temp = makeOne(arr, n//2) + 1
        arr[n] = temp if temp < arr[n] else arr[n]
    if n % 3 == 0:
        temp = makeOne(arr, n//3) + 1
        arr[n] = temp if temp < arr[n] else arr[n]

    return arr[n]


f = stdin.readline

n = int(f())
arr = [0 for _ in range(n+1)]
result = makeOne(arr, n)
print(result)

python code(Bottom UP)

# 백준 1463번
from sys import stdin
def makeOne(arr, n):
    for i in range(2, n+1):
        arr[i] = arr[i-1] + 1
        if i % 3 == 0:
            arr[i] = min(arr[i//3]+1, arr[i])
        if i % 2 == 0:
            arr[i] = min(arr[i//2]+1, arr[i])
    return arr[n]
    
f = stdin.readline

n = int(f())
arr = [0 for _ in range(n+1)]
result = makeOne(arr, n)
print(result)