백준 1463-1로 만들기 (파이썬)

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

1463번: 1로 만들기

 

문제

정수 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

---

시나리오

제시된 연산을 거쳐 정수 N을 1로 만들기 위해 필요한 최소 연산 횟수를 구하는 문제이다.

이 문제는 DP문제이다. DP의 원리는 이전 결과를 다음 결과에 이용하는 것이며 그렇기 때문에 점화식을 구하여 Top-Down 혹은 Bottom-up 구현법으로 푸는게 정석이다.

이 원리를 이번 문제에 적용해보자.

가장 작은 수 부터 1이 되게 하는데 필요한 횟수를 DP테이블에 저장해 가다가 어떤 정수가 2또는 3으로 나누어 떨어질 때 세가지 연산 중 어떤 연산을 해야 가장 적게 연산할지 알기 위해 DP테이블에 저장된 값(횟수)을 이용한다.

 

가령 x=10일 때, 10->9->3->1의 과정을 거쳐 1이 되는데

10은 -1 또는 2로 나눌 수 있기 때문에 cache[9]+1 과 cache[5]+1 중 더 작은 것을 cache[10]의 값으로 삼으면 되겠다.

cache[9]가 cache[5]보다 작기 때문에 전자를 cache[10]의 값으로 선택하게 되는데 이 때, 9는 -1 또는 3으로 나눌 수 있기 때문에 cache[8]+1과 cache[3]+1 중 더 작은 값을 cache[9]의 값으로 선택하게 되고 이 과정을 반복하는게 이번 문제의 풀이 방법이 되겠다.

다만 이번 풀이에서는 Bottom-up방식을 이용하기 때문에 cache[2]부터 cache[n]까지 차례로 구한다.

 

코드

#bottom-up
n = int(input())

#cache[k]==k를 1로 만들기 위한 연산 횟수
cache = [0] * (n + 1)

for i in range(2, n + 1):
	#i-1의 횟수 + 1
    cache[i] = cache[i - 1] + 1
	
    #3으로 나누어 떨어질 때,
    if not i % 3:
    	#i-1의 횟수 + 1 : i//3의 횟수 + 1 중 더 작은 값
        cache[i] = min(cache[i], cache[i // 3] + 1)
    #2와 3 모두를 약수로 갖는 정수일 경우 -1, 나누기 2, 나누기 3 세가지 연산 모두 비교해야 하므로 분기 하지않음
    if not i % 2:
    	#i-1의 횟수 + 1 : i//2의 횟수 + 1 중 더 작은 값
        cache[i] = min(cache[i], cache[i // 2] + 1)

print(cache[n])

다음 코드는 top-down으로 구현한 코드인데 제출하니 메모리 초과가 나왔다.

참고만 하도록 하자.

#top-down
import sys

n = int(input())

sys.setrecursionlimit(10 ** 6)
cache = [0] * (n + 1)


def make_one(num):
    if cache[num]:
        return cache[num]
    if num < 2:
        return cache[num]
    if not num % 3:
        cache[num] = min(make_one(num - 1) + 1, make_one(num // 3) + 1)
    if not num % 2:
        cache[num] = min(make_one(num - 1) + 1, make_one(num // 2) + 1)
    if num % 3 and num % 2:
        cache[num] = make_one(num - 1) + 1
    return cache[num]


print(make_one(n))