코틀린 코딩테스트 강좌, 동전 개수의 최솟값 구하기

이 글에서는 동전 개수를 최솟값으로 구하기 위한 알고리즘 문제를 다루고, 이를 해결하기 위한 코틀린 코드와 과정에 대해 자세히 설명하겠습니다.

문제 설명

우리는 다양한 동전의 가치를 가지고 있을 때, 일정한 금액을 만들기 위해 필요한 동전의 최소 개수를 구해야 합니다. 주어진 금액을 만드는 데 필요한 동전의 개수를 최소화하는 것이 목표입니다.

문제 입력:

동전의 종류 N (1 ≤ N ≤ 100)
각 동전의 가치 Aᵢ (1 ≤ Aᵢ ≤ 10,000)
목표 금액 M (1 ≤ M ≤ 1,000,000)

문제 출력:

목표 금액 M을 만드는 데 필요한 동전의 최소 개수를 출력합니다. 만약 만들 수 없다면 -1을 출력합니다.

예제

입력 예시:

출력 예시:

위의 예시에서는 동전의 종류가 3개이고, 각 동전의 가치는 1, 3, 4입니다. 목표 금액 6을 만들기 위해서는 2개의 동전을 사용하여 (3 + 3) 혹은 (4 + 1 + 1)를 만들 수 있습니다.

문제 해결 과정

이 문제를 해결하기 위해서는 동적 프로그래밍(Dynamic Programming)을 활용할 수 있습니다. 동적 프로그래밍은 이전의 결과를 재사용하여 문제를 해결하는 기법으로, 이 문제에서도 매우 유용하게 적용될 수 있습니다.

1. DP 배열 설정

먼저, 동전 개수를 저장할 DP 배열을 선언합니다. DP[i]는 금액 i를 만드는 데 필요한 최소 동전 개수를 의미합니다. 초기화할 때, DP[0]은 0으로 설정하고, 나머지 값은 무한대(INF)로 설정합니다.

2. 점화식 정의

각 동전의 가치에 대해 금액 M까지 반복하면서 DP 배열을 갱신합니다. 동전의 가치가 주어지면, 그 가치에서 시작하여 가능한 모든 금액에 대해 최소 동전 개수를 갱신합니다.

점화식은 다음과 같습니다:

        DP[j] = min(DP[j], DP[j - coin] + 1)

여기서 coin은 현재 고려하는 동전의 가치입니다.

3. 최종 결과 도출

모든 동전과 금액에 대해 DP 배열을 계산한 후, DP[M]을 확인하여 해당 값이 무한대(INF)인지 아닌지를 판단합니다. 만약 무한대라면 금액 M을 만들 수 없으므로 -1을 출력하고, 그렇지 않다면 DP[M]의 값을 출력합니다.

코드 구현


fun minCoins(coins: IntArray, target: Int): Int {
    // DP 배열을 무한대로 초기화
    val dp = IntArray(target + 1) { Int.MAX_VALUE }
    dp[0] = 0 // 0원을 만드는 데 필요한 동전은 0개

    // 각 동전의 가치에 대해 DP 배열 업데이트
    for (coin in coins) {
        for (j in coin..target) {
            if (dp[j - coin] != Int.MAX_VALUE) {
                dp[j] = Math.min(dp[j], dp[j - coin] + 1)
            }
        }
    }

    // 결과 확인
    return if (dp[target] == Int.MAX_VALUE) -1 else dp[target]
}

fun main() {
    // 입력 값
    val coins = intArrayOf(1, 3, 4)
    val target = 6
    val result = minCoins(coins, target)
    println(result) // 출력: 2
}

비교 및 최적화

이 알고리즘의 시간 복잡도는 O(N * M)이며, 공간 복잡도는 O(M)입니다. 동전의 종류가 많거나 목표 금액이 매우 큰 경우, 이 알고리즘은 시간적으로도 효율적입니다. 그러나 코드를 더 최적화할 수 있는 방법이 있습니다. 예를 들어, 동전의 가치를 내림차순으로 정렬한 뒤에 큰 동전부터 처리하는 방법이 있습니다. 이를 통해 더 빠르게 결과에 도달할 수 있습니다.

다양한 사례

여기서는 다양한 입력 값을 통해 알고리즘의 성능을 검증합니다. 여러 동전 종류와 금액 조합을 테스트하여 결과를 도출하는 것도 중요한 단계입니다.

사례 1:

입력: 4, 2, 5, 7, 목표금액 = 14

출력: 2 (2개의 7원을 사용)

사례 2:

입력: 1, 3, 4, 목표금액 = 11

출력: 3 (2개의 4원과 1개의 3원 사용)