[코테] 1로 만들기

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

1463번: 1로 만들기

 

처음 제출한 코드

import Foundation

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

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

print(dp[n])

>> 틀렸습니다.

 

틀린 이유는 else if로 작성했기 때문이다.

어떠한 경우에 2로 나누는 것이 더 작은 경우가 존재하기 때문이다.

ex) 642 

 

 

그 다음 작성한 코드

import Foundation

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

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

print(dp[n])

>> 런타임 에러

 

어제와 비슷한 이유로 런타임 에러가 발생했다.

n = 1일 때를 고려하지 않았다.

 

n = 1일때는 for문에서 끝나는 범위가 시작 범위보다 작기 때문에 오류가 발생한다.

 

 

최종 코드

import Foundation

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

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

print(dp[n])