[백준 11047번] [Kotlin] 동전 0

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

11047번: 동전 0

 

난이도 : 실버 4
태그 : 그리디

 

 

설명

그리디 알고리즘 문제로, 늘 최적의 해를 선택하는 문제입니다.

동전의 개수를 최소로 해야 하므로, 동전의 단위가 가장 큰 것부터 선택해야 합니다.

 

 

 

 

소스코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))

    val nk = br.readLine().split(" ")
    val n = nk[0].toInt()
    val targetPrice = nk[1].toInt()
    var nowPrice = 0

    val coin = Array(n) { 0 }

    repeat(n) {
        coin[it] = br.readLine().toInt()
    }

    var coinIdx = n - 1
    var coinCnt = 0

    while (nowPrice != targetPrice) {
        if (targetPrice < nowPrice + coin[coinIdx]) {
            coinIdx--
            continue
        }

        nowPrice += coin[coinIdx]
        coinCnt++
    }

    println(coinCnt)
}

 

targetPrice는 목표 금액,

nowPrice는 현재 금액입니다.

가장 단위가 큰 동전부터 하나씩 선택하며,

목표 금액보다 높다면 다음으로 작은 단위의 동전을 선택하며,

목표 금액과 같아질 때 까지 반복합니다.

 

 

후기

그리디 알고리즘을 연습하기 아주 좋은 문제였던 것 같습니다.