문제 링크 (opens new window)

풀이

1. 숫자 i를 1로 만드는 데에 소요된 최소 횟수를 구하기
2. 1번 로직은 3가지로 쪼개진다. i 3가 나누어떨어질때 i가 1로 만들어지기까지 최소 횟수, 2로 나누어떨어질때 1로 만들어지기까지 최소 횟수, i-1을 1로 만들기까지의 최소 횟수 세개 중 최솟값에 해당한다.

import Foundation

let N = Int(readLine()!)!
var d: [Int] = .init(repeating: 0, count: N+1)
d[0] = 0

if N == 1 {
    print(0)
    exit(0)
}

for i in 2...N {
    d[i] = d[i-1] + 1

    if i % 2 == 0 { d[i] = min(d[i], d[i / 2] + 1) }
    if i % 3 == 0 { d[i] = min(d[i], d[i / 3] + 1) }
}
print(d[N])

재풀이

1. DP 풀이는 완료
2. 불필요한 로직이 많이 고려되었음
3. i-1번째 값 먼저 불러오고, 2로 나누었을때 나머지와 3으로 나누었을때 나누어 떨어지는지 각각 체크하면 됨
4. 6으로 나누어 떨어지는건 굳이 체크 안하고, 2로 나누어 떨어지는 수와 3으로 나누어 떨어지는 수에 대해 각각 최소 연산횟수만 비교하면 됨

import Foundation

let N = Int(readLine()!)!
var dp: [Int] = .init(repeating: Int.max, count: 1000004)
dp[1] = 0
dp[2] = 1
dp[3] = 1

if N < 3 {
    print(dp[N])
    exit(0)
}

for i in 3...N {
    if i % 3 == 0 && i % 2 == 0 {
        dp[i] = min(dp[i / 3], dp[i/2], dp[i-1]) + 1
    } else if i % 3 == 0{
        dp[i] = min(dp[i / 3], dp[i-1]) + 1
    } else if i % 2 == 0 {
        dp[i] = min(dp[i / 2], dp[i-1]) + 1
    } else {
        dp[i] = dp[i-1] + 1
    }
}

print(dp[N])