백준 12852번 1로 만들기 2

정답 :

let n = Int(readLine()!)!

var array = Array(repeating: 0, count: 1000001)
var pre = Array(repeating: 0, count: 10000001)
var result : [Int] = []
array[1] = 0
if n == 1 {
    print(array[1])
    print(1)
}
else {
    for i in 2...n {
        array[i] = array[i-1] + 1
        pre[i] = i - 1
        if i % 3 == 0 && array[i] > array[i/3] + 1{
            array[i] = array[i/3] + 1
            pre[i] = i/3
        }
        if i % 2 == 0 && array[i] > array[i/2] + 1{
            array[i] = array[i/2] + 1
            pre[i] = i/2
        }
    }
    var res = n
    while true {
        result.append(res)
        if res == 1 {
            break
        }
        res = pre[res]
    }
    print(array[n])
    result.forEach{print($0,terminator: " ")}
}

TMI : 1로 만들기 1의 과정은 쉽게 기억해서 진행했지만, 경로를 추적하는 과정을 몰라서 아쉽게 보고 풀었다..

최소값을 구하는 과정은 기억하고 있어서, 쉽게 작성했지만, 경로 추적을 진행하는 과정을 몰라서 아쉽게도 풀지 못했다.. ㅠㅠ

 

그래도 이번 기회에 DP에 대해 많이 알게 된 것 같아 뿌듯하다. 더 어려운 DP 문제들이 남아있지만, 지금의 기억을 떠올려 어떻게든 열심히 해봐야겠다!