[BOJ/python] 12852: 1로 만들기 2

문제

✔️ silver 3
다이나믹 프로그래밍
그래프 이론
그래프 탐색

문제 흐름

DP를 활용해서 해결했다.
memo[x]에 x를 주어진 세가지 연산을 통해 1로 나타낼 경우 최소 연산의 수를 저장했고,
seq[x]에 그 과정을 저장했다.
처음에는 1 <= n <= 1000000이기 떄문에 seq에서 너무 메모리 초과가 나지 않을까 걱정했는데, 2로 나누거나 3으로 나누는 경우의 수만 몇번 나와도 수가 크게 감소하게 때문에 괜찮을거라 생각하고 진행했다.

1. 모든 원소가 각각 0, []로 초기화된 리스트 memo와 seq를 선언한다.
2. n이 1, 2, 3인 경우 바로 값을 리턴한다.
3. n이 1, 2, 3인 경우에 대해 초기값을 설정해준다.
4. 4부터 n까지의 x에 대해 5 ~ 7을 반복한다.
5. 리스트 calc에 세 연산중 가능한 연산에 대한 이전 연산 수(memo)과 그 인덱스를 넣는다.
6. calc를 계산값을 기준으로 연산 수 min_value와 그 인덱스인 m_idx를 구한다.
7. memo[x]에는 지난번 연산 수에 이번 연산을 카운트해준 min_value + 1,
   seq[x]에는 지난번 연산 과정 앞에 이번 수를 붙여준 [x] + seq[m_idx]를 넣어준다.
8. 각 결과를 출력한다.

코드

# 1로 만들기 2
# dp

import sys
input = sys.stdin.readline

def dp (n: int):
    memo = [0 for i in range(n + 1)]
    seq = [[] for i in range(n + 1)]
    if n == 1:
        return 0, [1]
    elif n == 2 or n == 3:
        return 1, [n, 1]
    memo[2] = 1
    memo[3] = 1
    seq[1] = [1]
    seq[2] = [2, 1]
    seq[3] = [3, 1]

    for x in range(4, n + 1):
        calc = [(memo[x - 1], x - 1)]
        if x % 3 == 0:
            calc.append((memo[x // 3], x // 3))
        if x % 2 == 0:
            calc.append((memo[x // 2], x // 2))
        min_value, m_idx = min(calc, key=lambda x: x[0])
        memo[x] = min_value + 1
        seq[x] = [x] + seq[m_idx]

    return memo[n], seq[n]

if __name__ == "__main__":
    n = int(input())
    
    result, seq = dp(n)
    print(result)
    print(*seq)

마무리

풀고나서 문제 유형을 살펴보니 그래프 탐색도 있었다.
계산 과정이 나와야 하니 그래프로도 풀 수 있겠구나 싶었다.
유형을 알아보는 눈을 기르는 것도 중요할 것 같다.