[BOJ] 1로 만들기 in Python & Kotlin

문제풀러 가기!

전형적인 DP 문제입니다. 물론 queue로도 접근할 수 있는거 같은데, 예외처리를 해줘야해서 조금 더 생각해볼만 했던 문제였습니다. 저는 아직도 dp라는 부분에서 memoization이라는 것이 와닿지는 않는 것 같습니다. 좀 더 연습이 필요하네요.

이런류의 문제를 정말 많이 만났지만, 항상 이런 문제는 어떻게 풀어야할지 좀 막막한게 있습니다. 그래서 이번엔 좀 많이 열심히 분석해보았어요.

문제의 키 포인트는 dp 배열을 만들고 이를 통해 연산 회수를 계속 저장하는 방법을 사용하는 것입니다. 그 규칙을 문제에서 주었구요. 이를 통해서 그 logic을 만들어가야 합니다.

문제 설명: n → 1로 만들어야 하는데 사용할 수 있는 연산은 아래 3가지 이다.

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

연산을 가장 적게 사용한 횟수를 구하라.

배열의 2번째 index부터 문제 조건의 최대 값인 1,000,000 index까지 연산을 하고 난 뒤에 답을 도출하는 것이 가장 이상적이라고 생각해요.

그리고 문제의 조건에 의해 계산되는 로직은 다음과 같아요.

2, 3의 최소 공배수인 6의 약수에 따라서 계산되는 식이 다릅니다.

6일 경우 1, 2, 3 연산
3일 경우 1, 3 연산
2일 경우 2, 3 연산
1일 경우 3 연산

그래서 Python의 경우 아래와 같이 코드를 짜면 됩니다.

dp = [0] * (10**6+1)
dp[1] = 0
for i in range(2, 10**6+1):
    if i % 6 == 0: dp[i] = min(dp[i//3]+1, dp[i//2]+1, dp[i-1]+1)
    elif i % 3 == 0: dp[i] = min(dp[i//3]+1, dp[i-1]+1)
    elif i % 2 == 0: dp[i] = min(dp[i//2]+1, dp[i-1]+1)
    else: dp[i] = dp[i-1] + 1
n = int(input())    
print(dp[n])

다음은 Kotlin 입니다.

import java.util.*

fun main() {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()

    val dp = IntArray(1000001){0}
    dp[0] = 0
    dp[1] = 0
    for (i in 2 until 1000001) {
        if (i % 6 == 0) {
            dp[i] = minOf(dp[i/2]+1, dp[i/3]+1, dp[i-1]+1)
        } else if (i % 3 == 0) {
            dp[i] = minOf(dp[i/3]+1, dp[i-1]+1)
        } else if (i % 2 == 0) {
            dp[i] = minOf(dp[i/2]+1, dp[i-1]+1)
        } else {
            dp[i] = dp[i-1] + 1
        }
    }
    println(dp[n])
}

어차피 내용은 똑같아서 이해하는데 어려움은 없으실 겁니다.

개발은 예술이고 서비스는 작품이다.