[백준] 1463번 : 1로 만들기 - Swift

문제

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

1463번: 1로 만들기

 

코드

1년전에는 Dynamic Programming에 대해서 아는 것이 없었다. 처음에는 반복문을 통해서 C++로 풀었다. 물론 틀렸다!🤦🏻‍♀️

이 문제는 DP로 Bottom-up 방식으로 풀어야한다.

Swift로 작성한 코드는 다음과 같다.

import Foundation

//1463

var num = Int(readLine()!)
var list = [Int](repeating: 0, count: num!+1)

for i in 2..<num!+1
{
    if(i <= 3){list[i] = 1}
    else
    {
        list[i] = list[i-1] + 1
    
        if (i%3 == 0 && list[i]>list[i/3] + 1)
        {
            list[i] = list[i/3] + 1
        }
        if (i%2 == 0 && list[i]>list[i/2] + 1)
        {
            list[i] = list[i/2] + 1
        }
    }
}

print(list[num!])

점화식은 min(list(N/3) +1, dp(N/2)+1, dp(N-1)+1) 이다.