1463번: 1로 만들기 - Kotlin

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

1463번: 1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

나의 풀이

 요즘 DP 문제를 접하고 있는데 DP 문제의 풀이 방식에 대한 기본적인 이해가 부족한 것 같아 쉬운 문제부터 풀어보고자 한다. DP의 기본적인 원리는 여러 개의 하위 문제를 먼저 해결하고 그 결과를 가지고 원하는 값을 얻는 원리이다. 그러므로 우리는 숫자 2부터 우리가 원하는 숫자인 N까지 차근차근하게 계산을 해서 dp 배열에 넣어야 한다. dp 배열에 저장되는 값은 해당하는 숫자까지 도달하려고 할 때 연산을 하는 횟수의 최솟값이다.

import kotlin.math.min

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()

    val dp = IntArray(n + 1)

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

    println(dp[n])
}

 위의 코드를 설명해 보겠다. i는 우리가 N까지 가야할때 불필요한 반복을 막기위해 필요한 수이다. 만약 우리가 원하는 값이 642 일때 어떤 방식으로 코드가 진행되는지 살펴보겠다.

 

1. dp[642] = dp[642 - 1] + 1

   일단 1을 뺀다. 641까지 도달하는데 필요한 횟수와 1일 빼는데 사용한 횟수 1을 더한다.

 2. if(642 % 2 == 0) dp[642] = min(dp[642], dp[642 / 2] + 1) 

    642가 2로 나누어 떨어짐으로 1번의 값과 (642 / 2 = 321)  321까지 도달하는데 필요한 횟수와 2로 나누는데 사용한 횟       수 1을 더한 값을 비교해 더 작은 값을 642까지 도달하는 횟수로 정한다.

 2. if(642 % 3 == 0) dp[642] = min(dp[642], dp[642 / 3] + 1) 

    642가 3으로 나누어 떨어짐으로 2번의 값과 (642 / 3 = 214) 214까지 도달하는데 필요한 횟수와 3으로 나누는데 사용한 횟수 1을 더한 값을 비교해 더 작은 값을 642까지 도달하는 횟수로 정한다.

 

 위의 설명은 bottom top(가장 작은 값부터 큰 값으로 가는 방식)방식인 코드를 이해하기 쉽게 top down(가장 높은 값부터 작은 값으로 가는 방식)방식으로 설명이다.