[백준] 1로 만들기 2

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

12852번: 1로 만들기 2

다이나믹 프로그래밍을 이용하는 문제입니다. 

 

우선 문제부터 요약하면, 3으로 나누거나, 2로 나누거나, 1을 빼는 총 3종류의 연산을 할 수 있을 때, 연산을 해서 1을 만들 수 있는 횟수의 최솟값을 return 해야 합니다. 또한 이렇게 최소 횟수로 진행되는 경우에 등장하는 숫자도 return 해야 합니다.

 

이 문제는 숫자를 return해야 하는 과정이 조금은 까다로운데 설명해 보도록 하겠습니다. 

 

<Solution>

Dynamic programming의 코드를 작성 할 때는 2가지의 방법을 이용하는데 top-down, bottom-up 이렇게 두가지의 방법이 있습니다. 

 

우선 dp table을 만듭니다. 이 dp table은 각각의 숫자에 대해 1로 가는 최솟값을 담습니다. 

 

다음과 같이 구현 할 수 있습니다.

<Bottom-up> 

import sys

num = int(sys.stdin.readline().rstrip())

# build dp table
dp = [int(2e9)]* (num+1)
dp[1] = 0
# for answer
answer_list = []
for i in range(2,num+1):
    to_append = i - 1
    if i%3 == 0:
        dp[i] = min(dp[i], dp[int(i/3)]+1)
    if i%2 == 0:
        dp[i] = min(dp[i], dp[int(i/2)]+1)
    dp[i] = min(dp[i], dp[i-1]+1)

print(dp)

<Top-down>

import sys

num = int(sys.stdin.readline().rstrip())

# <Top - down>
dp = [int(2e9)]* (num+1)
dp[1] = 0

def times(num):
    if dp[num] != int(2e9):
        return dp[num]
    search_list = []
    if num % 3 == 0:
        search_list.append((times(int(num/3)),int(num/3)))
    if num % 2 == 0:
        search_list.append((times(int(num/2)),int(num/2)))
    search_list.append((times(num-1),num-1))
    tmp = min(search_list, key = lambda x: x[0])
    dp[num] = tmp[0] + 1

    return dp[num]

times(num)
print(dp)

이 때, 우리는 결과 값 뿐만 아니라 중간에 어떤 숫자들을 거쳐서 1이 만들어 지는지 또한 return 해야 하므로 

# to find path
parent = [i for i in range(num+1)]

각 결과가 어떤 부모로 부터 나왔는지를 담는 array를 만들어 주고, 이 array에 정보를 저장하는 형태로 구현하였습니다. 

 

실제 구현된 전체 코드는 아래와 같습니다.

(물론 Top down의 재귀함수를 호출하는 방식보다 Bottom up 방식이 시간측면에서는 이득일 것입니다. Bottom up 방식도 동일하게 구현하면 돌아 갈 것입니다.)

import sys
sys.setrecursionlimit(10**6)
num = int(sys.stdin.readline().rstrip())

# <Top - down>
dp = [int(2e9)]* (num+1)
dp[1] = 0

# to find path
parent = [i for i in range(num+1)]

def times(num):
    if dp[num] != int(2e9):
        return dp[num]
    search_list = []
    if num % 3 == 0:
        search_list.append((times(int(num/3)),int(num/3)))
    if num % 2 == 0:
        search_list.append((times(int(num/2)),int(num/2)))
    search_list.append((times(num-1),num-1))

    tmp = min(search_list, key = lambda x: x[0])
    # for tracing path
    parent[num] = tmp[1]
    dp[num] = tmp[0] + 1

    return dp[num]

print(times(num))
# print(dp)
# print(parent)
# rebuild path
path = [num]
index = num
while(parent[index] != index):
    path.append(parent[index])
    index = parent[index]

print(' '.join(map(str,path)))