[Swift] 백준_1로 만들기 2(12582)

문제

 

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

12852번: 1로 만들기 2

 

 

풀이

 

1로 만들기 문제와 푸는 법은 동일하지만 경로를 구해야한다.

 

numbers라는 배열을 만들어 각 경우에서 이전 값이 어떤 값이 었는지 추가해주었따. 이렇게 하면 numbers[k]는 k 이전의 값이므로 반복문을 통해 경로를 추적할 수 있다.

import Foundation

let n = Int(readLine()!)!
var result = Array(repeating: 0, count: n + 1)
var numbers = [0,1]
if n == 1 {
    print(0)
    print(1)
    exit(0)
}
for i in 2...n {
    var check = 0
    result[i] = result[i - 1] + 1
    check = i - 1
    if i % 2 == 0 {
        result[i] = min(result[i], result[i / 2] + 1)
        if result[i] > result[i / 2] {
            check = i / 2
        }
    }
    if i % 3 == 0 {
        result[i] = min(result[i], result[i / 3] + 1)
        if result[i] > result[i / 3] {
            check = i / 3
        }
    }
    numbers.append(check)
}
print(result[n])
var count = n
var temp = ""
for _ in 0...result[n] {
    temp += "\(count) "
    count = numbers[count]
}
print(temp)

 

 

_____________________________________________________________________________________________________

 

어려워. 더 효율적으로 짜는 것도 생각해봐야할듯