문제
동빈이는 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