그리디 알고리즘 : 만들 수 없는 금액 [이코테 314P, Kotlin]

문제

동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액중 최솟값을 구하는 프로그램을 작성하세요.
예를 들어, N = 5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9월짜리 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다. 

 

출력조건
첫째 줄에는 동전의 개수 N이 주어집니다. ( 1 <= N <= 1,000)
둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분한다. 각 화폐 단위는 1,000,000 이하의 자연수입니다.

 

입력조건
만들 수 없는 양의 정수 금액중 최솟값을 출력합니다.

 

첫 번째 시도 + 생각한 나의 풀이 

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

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val num = br.readLine().toInt()
    val coinList = mutableListOf<Int>()
    br.readLine().split(" ").forEach{
        coinList.add(it.toInt())
    }
    coinList.sortDescending()
    repeat(coinList.first() * num){  // 양의 정수를 찾는 반복
        for(i in 1 until coinList.size) {
            var resultNum = it
            for (j in i until coinList.size) {
                if (resultNum >= coinList[j]) { // 현재 수가 양의 정수 보다 이하일 때
                    resultNum -= coinList[j]
                }
            }
            if(resultNum == 0){
                break
            }
            if(i == coinList.size - 1){
                print(it)
                return
            }
        }
    }
}

동전을 내림차순으로 정렬한 후, 최댓값 * 총 개수 만큼(임의의 횟수) 반복한다. 반복할 때마다 현재 반복 횟수를 만들 수 있는지 확인한다. 만들 수 없다면 출력한다. 
해당 알고리즘에서 Target을 가지고 있는 화폐로 만드는 방법은 Target을 가지고 있는 화폐중 가장 큰 수부터 빼서 0이 도출되는지 확인하는 방법으로 Target을 만들 수 있는지 확인하였다. (당연하게도 틀린 방법, Target이 4이고 가진 동전이 1, 2, 3이면 4를 만들 수 없다.)  

 

두 번째 시도

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

fun main(){

    val br = BufferedReader(InputStreamReader(System.`in`))

    val num = br.readLine().toInt()
    val coinList = br.readLine().split(" ").map{ it.toInt() }.sorted()
    var target = 1

    // 현재 얻은 화폐의 합까지 모두 만들 수 있다고 가정,
    // 만약 모든 합 target 보다 다음 숫자가 큰 경우
    for(coin in  coinList) {
        if(target < coin) {
            break
        }else {
            target += coin
        }
    }
   	print(target)
}

현재까지 얻은 화폐의 합까지 만들 수 있다고 가정하고, 만약 다음 타겟이 화폐의 합보다 큰 경우 다음 화폐를 더한다, 이 때 현재까지 화폐의 합보다 다음 화폐가 큰 경우 현재 화폐와 다음 화폐간의 간격이 발생하고, 해당 간격은 얻어질 수 없다. 위의 코드의 관점에서 target은 현재 화폐까지의 합 + 1이다. 다음 coin이 target보다 작은 경우 target에 coin을 더하여 업데이트를 하고, 만약 다음 coin이 target보다 크다면 멈추고 target을 출력한다. 

 

https://github.com/jeongjaino/Problem_solving/blob/master/src/main/kotlin/day1/Day1-4.kt