[알고리즘] 1 만들기

1로 만들기 문제

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
1. X가 5로 나누어 떨어지면, 5로 나눈다.
2. X가 3으로 나누어 떨어지면, 3으로 나눈다.
3. X가 2으로 나누어 떨어지면, 2로 나눈다.
4. X에서 1을 뺀다.

위의 연산 4가지를 적절히 사용해서 1을 만들려고 한다.
연산을 사용하는 횟수의 최솟값을 출력하시오.

example

X = 26
1. 26 - 1 = 25
2. 25 / 5 = 5
3. 5 / 5 = 1

answer = 3

체크해야할 점

dp 인지 체크해야만 한다.

1. 큰 문제를 작은 문제로 나눌 수 있는가?

그러하다. 해당 문제는 큰문제를 작은 문제로 분할 할 수 있다.
5 연산을 수행하면, 25 // 5 를 진행하면 해당 연산을 1회 줄일 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

위와 동일

풀이 방법

해당 연산을 그냥 재귀적으로 풀려면 많은 시간이 소요 되므로 반드시 dp를 사용해야만 한다.

Solution

topdown 방식 with memoization.

d = [None] * 30001 # 메모할 공간을 선언한다.
def topdown(n: int, d: list[int]) -> int:
    if n == 1:
        d[1] = 0
        return d[1]
    else:
        ### 이미 계산되어 있는 경우
        if d[n] is not None:
            return d[n]
        ### 계산되어 있지 않은 경우
        else:
            answer = n
            if n % 2 == 0: # n이 2로 나뉘는 경우
                answer = min(answer, topdown(n//2, d)+1)
            if n % 3 == 0: # n이 3으로 나뉘는 경우
                answer = min(answer, topdown(n//3, d)+1)
            if n % 5 == 0: # n이 5로 나뉘는 경우
                answer = min(answer, topdown(n//5, d)+1)            
            # 최종 정답을 d[n]에 저장한다.    
            d[n] = answer
            return d[n]

위의 방식은 불필요한 연산이 많이 포함이 된다. 때문에 해당 방식은 왠만해서는 자제하는 것이 좋다.

bottom up 방식

def make_1(n):
    d = [0] * 30001
    for i in range(2, n+1):
        # 현재의 수에서 1을 빼는 경우
        d[i] = d[i - 1] + 1 
        # 2로 나누어 떨어지는 경우
        if i % 2 == 0:
            d[i] = min(d[i], d[i // 2] + 1) #마지막에 1을 더하는 이유는 해당 함수를 호출 했기 때문
        # 3로 나누어 떨어지는 경우
        if i % 3 == 0:
            d[i] = min(d[i], d[i // 3] + 1)
        # 5로 나누어 떨어지는 경우
        if i % 5 == 0:
            d[i] = min(d[i], d[i // 5] + 1)
    
    return d[n]

해당 방식의 장점은 불필요한 함수를 호출할 필요가 없다.
우리는 그냥 전체적으로 탐색을 진행하면 된다. 따라서 시간 복잡도는 O(n)이다.