[백준 1436번] [Kotlin] 1로 만들기

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

1463번: 1로 만들기

난이도 : 실버 4
태그 : 다이나믹 프로그래밍

 

 

설명

 

동적계획법 (다이나믹 프로그래밍)을 이용해 풀 수 있는 문제입니다.

 

2로 나누기, 3으로 나누기, 1 빼기 중 하나를 통해 1로 만들 수 있는 최소한의 연한 횟수를 구하는 문제인데,

 

그리디(탐욕법)으로 생각할 수 있으나, 때로는 무조건 3으로 나누는 것이 더 효과적이지 않을 수 있습니다.

 

 

---

소스코드

import kotlin.math.min

fun main() {
    val n = readLine()!!.toInt()

    val dp = Array(n + 1) { 0 }
    dp[1] = 0

    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)
    }

    print(dp[n])
}

 

다이나믹 프로그래밍 변수를 담을 dp 배열을 생성합니다.

해당 문제에서는 1부터 시작하기 때문에, 인덱스를 이에 맞추기 위해

n+1만큼의 크기를 dp 배열로 설정합니다.

 

이후 1부터 n까지의 모든 수에 대해

해당 값의 최소 연산 횟수를 구합니다.

 

 

 

가장 적은 연산횟수 구하기

dp[i] = dp[i - 1] + 1

첫번째로 이전 값의 +1 한 값으로 초기화를 합니다.

 

1을 빼는 연산을 역으로 계산한 것입니다.

 

 

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

그 다음으로 2로 나눴을때의 경우를 고려해봅시다.

현재 값이 2의 배수일때 (i%2 == 0) dp[i/2]의 값과 현재의 값을 비교해 작은것을 선택합니다.

 

 

if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1)

 

마지막으로 3으로 나눴을때의 경우를 고려해봅시다.

현재의 값이 3의 배수일때 (i%3 == 0), dp[i/3]의 값과 현재의 값을 비교해 작은것을 선택합니다. 

 

 

print(dp[n])

 마지막으로 dp[n]의 값을 출력합니다.

 

---

후기

처음으로 풀어보는 다이나믹 프로그래밍 문제입니다.

 

다이나믹 프로그래밍이라 해서 동적으로 뭔가를 하는 건줄 알았더니,

 

알고보니 Dynamic은 그냥 별 의미 없이 붙은거라 하더군요...

 

꽤 재밌게 풀었던 문제였던 것 같습니다.