[이코테] 그리디 알고리즘 - 만들 수 없는 금액 코틀린 코드

fun main() {
    val n = 5
    val coins = mutableListOf(3, 2, 1, 1, 9)

    coins.sort()

    var target = 1
    for (i in 0..<n) {
        if (coins[i] > target) break
        target += coins[i]
    }

    println("target = $target")
}

 

처음에는 완전 탐색으로 접근해야하나? 라는 생각이 들었다.

(물론 책 카테고리가 그리디 알고리즘이지만 내가 문제를 보고 제일 먼저 드는 생각은 완전 탐색이었다.)

target이 1씩 증가하면서 최솟값을 찾아야겠다는 생각 때문에

 

근데 완전 탐색의 경우

N개의 동전으로 만들 수 있는 모든 부분집합을 고려하면 부분집합 개수는 2^N 개

N이 최대 1,000개면 최악의 경우 2^1000 → 연산 불가능하다고 판단했다.

단순히 1부터 만들 수 있는 금액을 순회하면서 찾으려고 해도, 매번 가능한 동전 조합을 체크해야 해서 비효율적이다.

 

그래서 결국 그리디로 풀어야하는데

이 문제의 핵심은

 

• 작은 동전부터 사용하면 "만들 수 있는 금액의 범위"를 점진적으로 확장할 수 있다.
  • 정렬된 동전을 하나씩 추가하면서 만들 수 있는 금액의 범위를 확장하면 항상 최적의 방법을 보장할 수 있다.
• 항상 "연속된 범위(target-1 이하)를 유지하면서 진행할 수 있다."
  • 작은 동전부터 추가하면, 1 ~ target-1 범위를 유지한 채 점진적으로 확장된다.
  • 이 과정에서 target보다 큰 동전이 나오면 만들 수 없는 최소 금액이 확정된다.
• 정렬 후 단순히 target만 갱신하면서 진행하면 된다!
  • 각 동전을 하나씩 보면서 target을 증가시키는 방식 → 최적해 보장
  • 즉, 매 순간 "현재 동전으로 기존의 target을 확장할 수 있는가?" 만 체크하면 된다.

 

 

 

따라서 문제를 보고 그리디 알고리즘으로 접근을 떠올리는 과정은 다음과 같다.

Step 1️⃣: "모든 조합을 고려하면 너무 많다" → 완전 탐색 불가능!

• "N개의 동전으로 만들 수 있는 모든 금액을 조사하면 될까?"
  → 부분집합 개수가 2^N개라서 완전 탐색은 불가능
  → 더 효율적인 방법이 필요하다!

Step 2️⃣: "그리디 접근이 가능한지 확인"

• "작은 동전부터 사용하면 점진적으로 만들 수 있는 금액을 확장할 수 있지 않을까?"
  → 정렬 후 작은 값부터 사용하면, 항상 최적해를 보장할 수 있음

Step 3️⃣: "연속된 금액(target-1 이하)을 유지하면서 확장하는 방법?"

• 처음엔 target = 1 (아무것도 만들 수 없는 상태)
• 동전을 하나씩 추가하면서 만들 수 있는 금액의 범위를 확장
• "현재 동전이 target보다 크다면, target 값을 만들 수 없음!"

Step 4️⃣: 최적해 보장 여부 확인

• 작은 동전부터 차례로 보면 이전까지 만들 수 있던 금액 + 현재 동전으로 연속된 범위 유지 가능
• 새로운 동전이 target보다 크면 만들 수 없는 최소 금액이 결정됨

💡 즉, "최소 동전부터 하나씩 보면서 target을 늘려가면 최적해를 보장할 수 있다!"
➡️ 그리디 전략이 가능하다는 걸 확신할 수 있다! 🚀