백준 - 동전 0

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/11047

 

[문제 설명]

동전을 최소한 사용해서 금액을 만들어라.

 

[접근 방법]

매우 자주 나오는 그리디 대표 문제.

단, 조건을 무조건 확인하고 풀어야 한다. 

위와 같은 조건이 없다면 다른 방법을 찾아봐야 한다.

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (N, K) = readLine().split(" ").map { it.toInt() }
    val arrOfCoin = IntArray(N) { readLine().toInt() }

    // 남은 비용
    var remainCost = K
    // 현재 사용할 동전의 인덱스
    var idx = arrOfCoin.size - 1
    // 현재 사용한 동전 개수
    var cntOfCoin = 0
    // while : 남은 금액이 0보다 큰동안
    while (remainCost > 0) {
        // 만약, 동전을 다썼는데 돈이 남으면 거스를 수 없는 금액이다.
        if (idx !in arrOfCoin.indices) {
            cntOfCoin = -1
            break
        }

        // 사용한 동전 개수 추가
        cntOfCoin += (remainCost / arrOfCoin[idx])
        // 거슬러준만큼 남은 금액 빼기
        remainCost -= arrOfCoin[idx] * (remainCost / arrOfCoin[idx])
        // 동전의 인덱스 감소
        idx--
    }

    println(cntOfCoin)
}