[백준] 11047. 동전 0 (Kotlin)

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

11047번: 동전 0

 

 

 

풀이

 

// [백준] 11047. 동전 0 (Kotlin)

import java.util.*

var sum = 0

fun main() = with(Scanner(System.`in`)){
    val n = nextInt()
    var k = nextInt()

    val arr = Array(n){0}

    for(i in 0 until n){
        arr[i] = nextInt()
    }

    // 하행연산
    for(i in n-1 downTo 0){
        val tmp = k/arr[i]
        sum += tmp
        k -= tmp*arr[i]
    }

    println(sum)
}

Ai는 Ai-1의 배수라는 조건이 있기 때문에

 

n 1일 때 => 1

n 2일 때 => x  라고 가정하면

 

n 3일 때 => q1x 

n 4일 때 => q2(q1x) 

n 5일 때 => q3(q2(q1x))

 

(q는 임의의 자연수)

 

의 형태가 반복될 것이다. 큰 동전은 자기보다 작은 동전을 포함하고 있기 때문에 무조건 가능한 한 큰 동전을 사용하는 것이 최소 횟수이다.

그래서 뒤부터 연산을 해주면 된다.

 

만약 Ai는 Ai-1의 배수라는 조건이 없다면 ?

n = 3, k = 12

1

4

5

 

라고 주어졌다면 하행 연산을 하면 5 동전 2개, 1동전 2개를 사용해야 하지만

최소 횟수는 4 동전을 3개 사용하는 것이다.

 

따라서 저 조건이 없다면 다른 방식으로 풀어야 할것이다.