백준 - 1로 만들기 (1463)

let N = Int(readLine()!)!
var dp = Array(repeating: 0, count: N + 1)

// dp 테이블 초기화
dp[1] = 0
if N > 1 { dp[2] = 1 }
if N > 2 { dp[3] = 1 }

// 점화식
for i in stride(from: 4, through: N, by: 1) {
    dp[i] = dp[i - 1] + 1
    if i % 2 == 0 {
        dp[i] = min(dp[i], dp[i / 2] + 1)
    }
    if i % 3 == 0 {
        dp[i] = min(dp[i], dp[i / 3] + 1)
    }
}

print(dp[N])

특정 수 x의 연산 횟수의 최솟값은 1. x - 1의 최소 연산 횟수 + 1 , 2. x / 2의 최소 연산 횟수 + 1 , 3. x / 3의 최소 연산 횟수 + 1 중 가장 작은 값이다. 이때 2와 3은 나누어 떨어질 때만 비교할 수 있다.

이를 사용해서 1부터 N까지 각 연산 횟수의 최솟값을 구하고 dp 테이블에 저장한 후 N의 최솟값을 출력한다.