[백준] 1463번: 1로 만들기 - Kotlin[코틀린]

문제

 

1463번: 1로 만들기

 

---

풀이

 

N을 만들기 위한 3가지 방법은 다음과 같다.

 

1. N가 3으로 나누어 떨어지면, 3으로 나눈다.
2. N가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

 

이를 식으로 표현하면,

 

1. dp[n] = dp[n/3] + 1

2. dp[n] = dp[n/2] + 1

3. dp[n] = dp[n-1] + 1

 

이고, 3나누기 ->  2나누기 -> 1빼기의 차례대로 연산을 사용하는 횟수가 적어질 것이다.

따라서 우선 dp[n]을 dp[n-1] + 1인 경우로 저장하고, 2의 배수이면 dp[n/2] + 1, 3의 배수이면 dp[n/3] + 1 으로 계산해준다.

 

---

코드

 

import kotlin.math.min

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val num = br.readLine().toInt()
    val dp = IntArray(num + 1)

    for(i in 2 .. num) {
        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)
    }

    bw.write("${dp[num]}")
    bw.flush()
    bw.close()
    br.close()
}