[Python/Kotlin] 백준 1463번 : 1로 만들기

백준 문제 주소 https://www.acmicpc.net/problem/1463

문제

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

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

10

출력

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

3

---

이번 문제는 연산을 하는 횟수의 최솟값을 원하기 때문에, 배열을 하나 만들어서 min 함수로 최솟값을 찾은 다음에 저장하면 되겠다고 생각했다.
10 -> 9 -> 3 -> 1로 이어지는 연산이 큰 수로 나누면 가장 빠를 것이라는 내 편견을 부순 예제였다.
큰 수에서 1을 빼거나 2로 나누거나 3으로 나누는 기능을 부르는 것보다, 1부터 시작해서 계산하는 상향 방식이 맞는 것 같다고 생각했다.

Python 풀이

n = int(input())
arr = [0 for _ in range(n+1)]

for i in range(2, n+1):
    arr[i] = arr[i-1] + 1

    if i % 2 == 0:
        arr[i] = min(arr[i], arr[i//2]+1)
    if i % 3 == 0:
        arr[i] = min(arr[i], arr[i//3]+1)

print(arr.pop())

배열에 담긴 것은 연산을 하는 횟수의 최솟값이다. 따라서 반복문을 돌리는 동안 +1씩 추가해 주는 것은 연산 횟수이다.
만약 i가 6이라면 첫번째 if문을 통과하기 때문에 arr[6]은 arr[6]과 arr[3]+1 중에 작은 것으로 값이 저장되는 구조이다.
오른쪽 arr[6]은 arr[5]의 값에서 1을 더한 값으로 4이다. 그리고 arr[3]은 1이므로 4와 2중에 작은 값인 2가 되는 것이다.

6 > 3 > 1 (연산횟수 : 2)

Kotlin 풀이

import java.io.*

fun main(args: Array<String>)
{
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val arr = Array(n+1){0}

    for (i in 2..n) {
        arr[i] = arr[i-1] + 1

        if (i % 2 == 0) {
            arr[i] = Math.min(arr[i], arr[i/2]+1)
        }
        if (i % 3 == 0) {
            arr[i] = Math.min(arr[i], arr[i/3]+1)
        }
    }
    println(arr[n])
}