정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
상향식 DP 를 사용하려고 생각했다.
구하고자 하는 값이 횟수의 최솟값이므로 DP Table (1차원 배열) 의 값은 최솟값을 저장한다.
- A[1] = 0
- 1 은 그 자체가 1 이므로 연산횟수는 0 이다.
- A[2] = 1
- 2 는 -1 혹은 /2 하면 1 이 되므로 최소 연산횟수는 1 이다.
- A[3] = 1
- 3 은 /3 의 경우에 1 이 되므로 최소 연산횟수는 1 이다.
- 4 이후로는 /3 혹은 /2 혹은 -1 한 값의 최솟값에 각 +1 을 한 뒤 그 중 최솟값을 저장한다.
- A[4/3] 은 불가능 하므로 패스, A[4/2] = A[2] = 1 이고 +1 하여 2,
A[4-1] = A[3] = 1 이고 +1 하여 2- Min(불가능, 2, 2) 하여 A[4] = 2
- 이런 식으로 문제의 예시에 나온 10 을 계산해보면
- A[10/3] = 불가능, A[10/2] = A[5] = 3, A[10-1] = A[9] = 2
- 따라서, A[10] = Min(불가능, 4, 3) = 3
const val INF = 987654321
fun main(args: Array<String>) {
val N = readLine()!!.toInt()
val dp = IntArray(10000001) {INF}
dp[1] = 0
dp[2] = 1
dp[3] = 1
for (i in 4..N) {
if (i%3 == 0) {
dp[i] = Math.min(dp[i/3]+1, dp[i])
}
if (i%2 == 0) {
dp[i] = Math.min(dp[i/2]+1, dp[i])
}
dp[i] = Math.min(dp[i-1]+1, dp[i])
}
println(dp[N])
}