[Baekjoon] DP - 12852 1로 만들기 2

문제

12852번: 1로 만들기 2

 

풀이

1. 1로 만들기의 응용으로 생각하여 1로 만들기의 뼈대를 활용하였다.

2. 최소값을 구하는 부분에서 어떤 값을 선택할 지가 주된 문제이다.

3. DP는 큰 문제를 작은 문제로 해결할 수 있기 때문에 연속된 참조하고 있다.

  3-1. 10인 경우 9와 5중 1로 만들 수 있는 경우의 수 중 작은 값을 선택한다.

  3-2. 이 때, 9는 다음으로 3을 참조하고 5는 4를 참조한다.

  3-3. 이를 반복하여 최종 결과물은 10 -> 9 -> 3 -> 1이 등장하게 된다.

4. 해당 참조를 구하기 위한 값을 따로 저장했다. (answer)

 

n = int(input())
d = [987654321] * (n + 1)


def solution(n, d):
    result = [0] * (n + 1)
    d[1] = 0

    for i in range(2, n + 1):
        min_value = n + 2

        if not i % 3 and d[i] > d[i // 3] + 1:
            d[i] = d[i // 3] + 1 
            min_value = i // 3

        if not i % 2 and d[i] > d[i // 2] + 1:
            d[i] = d[i // 2] + 1
            min_value = i // 2

        if d[i] > d[i - 1] + 1:
            d[i] = d[i - 1] + 1
            min_value = i - 1

        result[i] = min_value

    value = n
    ansewr = [n]

    while value:
        if result[value] == 0:
            break

        ansewr.append(result[value])
        value = result[value]

    return ansewr


answer = solution(n, d)
print(len(answer) - 1)
print(*answer, sep=' ')

 

채점 결과