[BOJ] 12852. 1로 만들기 2 (Python)

12852번: 1로 만들기 2

 

다이나믹 프로그래밍의 bottom-up 방식으로 풀 수 있는 가장 대표적인 문제 중 하나인 1로 만들기!

문제도 간단, 아이디어도 간단하다.

X라는 숫자를 1로 만들기 위해서 할 수 있는 작업은 아래와 같다.

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

이는 반대로 생각하면 X라는 숫자를 만들기 위해서 할 수 있는 일은 다음과 같다고 볼 수 있다.

1. X / 3인 숫자에 3을 곱해서 X를 만든다.
2. X / 2인 숫자에 2를 곱해서 X를 만든다.
3. X-1인 숫자에 1을 더한다.

그럼 이제 우리는 2부터 X까지 각각 숫자를 만들 수 있는 방법의 최소 연산 수를 구해보면 된다.

예를 들어

 

2를 만드는 방법

1) 1 + 1 -> 연산 수 : 1

-> 최소 연산 수 :  1

 

3을 만드는 방법

1) 2 + 1  = (1 + 1) + 1  -> 연산 수 : 2

2) 1 * 3 -> 연산 수 : 1

-> 최소 연산 수 : 1

 

4를 만드는 방법

1) 3 + 1 = (1 * 3) + 1 -> 연산 수 : 2

2) 2 * 2 = (1 + 1) * 2 -> 연산 수 : 2

-> 최소 연산 수 : 2

 

...

 

이런 식으로 X까지 구해주면 된다!

 

그런데 문제의 조건을 보면 "1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다." 라는 조건이 있다. 

이 역시 간단하다.

배열을 하나 더 만들어서 타겟 숫자가 어떤 숫자에 연산을 했을 때 최소 연산 횟수로 만들어지는지를 저장해두면 된다.

아래 코드에서 how라는 배열이 그 역할을 해주고 있다.

마지막에 how[num]에서 거꾸로 따라가면 어떤 숫자를 거쳐 만들어졌는지 구할 수 있다.

 

n = int(input())
INF = int(1e9)
array = [INF] * (n+1)
how = [0] * (n+1)
array[1] = 0
how[1] = [1]

for i in range(2, n+1) :
    # 3 곱하기
    if i % 3 == 0 :
        prev = array[i]
        array[i] = min(array[i], array[i//3] + 1)
        if array[i] != prev :
            how[i] = i//3
    # 2 곱하기
    if i % 2 == 0 :
        prev = array[i]
        array[i] = min(array[i], array[i//2] + 1)
        if array[i] != prev :
            how[i] = i//2
    # 1 더하기
    prev = array[i]
    array[i] = min(array[i], array[i-1] + 1)
    if array[i] != prev :
        how[i] = i-1

print(array[n])

num = n
print(num, end = ' ')
while num != 1 :
    print(how[num], end = ' ')
    num = how[num]