[ 백준 1463 ] - 1로 만들기 (Kotlin)

 

 

1463번: 1로 만들기

 

문제 이해 & 기본 개념

• 아래 3가지 방법을 통해 입력 받은 수를 1로 만드는 것
  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.
• 최소 횟수를 구해야하는 문제
• 3으로 나누는게 1을 빼는 것보다 수가 훨씬 작아지므로 자칫하면 그리디 문제로 오해할 수 있다.

ex) n = 10
10 -> 9 -> 3 -> 1
10 -> 5 -> 4 -> 2 -> 1

• 이처럼 가능한 큰 수로 나누는 것보다 1을 먼저 빼는 경우가 최소 횟수가 될 수도 있기 때문에 dp를 이용한다.

 

---

최종 풀이

• 파란색이 처음 계산 되는 부분
• 빨간색이 중복 계산 되는 부분
• 노란색이 최적의 해
• DP를 이용해서 빨간 부분들의 중복을 제거한다고 보면 된다.

dp[i] = min(dp[i/3], dp[i/2], dp[i-1]) + 1

• i 번째 수에서 가능한 3가지 경우 중 최소 값 + 1이 i번 째의 최소 횟수가 된다.

---

 

소스 코드

1. 상향식 기법 

• 아래부터 위로 계산하는 방법

import kotlin.math.min

lateinit var dp:Array<Int>

// 상향식 방법
// dp[i] = min(dp[i-1], dp[i/3], dp[i/2]) + 1
fun solve(x:Int):Int {
    for (i in 2 until x + 1){
        // 아래 3가지의 경우 중 최솟값이 dp[i]에 들어가게 됨
        dp[i] = dp[i-1] + 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)
    }
    return dp[x]
}

fun main(){
    val n = readln().toInt()
    dp = Array<Int>(n+1){ 0 }
    println(solve(n))
}

 

2. 하향식 기법

• 위에서 아래로 계산하는 방법

import kotlin.math.min

lateinit var dp:Array<Int>

fun solve(x:Int, cnt:Int):Int{
    if(x == 1) return cnt

    if(x % 3 == 0 && dp[x/3] > cnt) dp[x/3] = min(solve(x/3, cnt+1), dp[x/3])
    if(x % 2 == 0 && dp[x/2] > cnt) dp[x/2] = min(solve(x/2, cnt+1), dp[x/2])
    if(dp[x-1] > cnt) dp[x-1] = min(solve(x-1, cnt+1), dp[x-1])

    dp[x] = min(min(dp[x/3], dp[x/2]), dp[x-1])
    return dp[x]
}

fun main(){
    val n = readln().toInt()
    dp = Array<Int>(n+1){ 1000001 }
    println(solve(n,0))
}