Kotiln] 백준 9084번 풀이

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

9084번: 동전

 

이 문제도 DP 문제이다..

 

이 문제를 동전을 몇 개를 쓰느냐의 문제이다. 즉, 경우의 수 문제이다.

간단하게, 1 2 5 세 개의 동전으로 10을 맞춘다 생각해보자.

 

1의 동전으로 10을 맞추는 법을 보자.

1은 1을 1개 넣는 법,, 즉 1가지. 2는 2개 넣는법,, 1가지. 3개는 3개 넣는법,, 1가지.. 이렇게 된다.

즉, 10 모두 한 가지 방법을 가진다.

1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1

 

다음 2의 동전으로 만들어보자. 근데 dp이므로 이전 테이블을 그대로 활용한다.

2의 경우 1의 동전을 2개 사용하는 케이스, 그리고 2의 동전 1개를 사용하는 케이스가 추가된다. 따라서 +1이 된다.

3의 경우, 1의 동전 3개과 1의 동전 1개, 2의 동전 1개를 맞춰서 만드는 케이스, 두 가지가 생긴다.

두번째 케이스를 보자. 즉, 2를 뺐을 때 1원이 남게 된다. 이 말인 즉슨 2원을 뺀 1원이 됐을 때 만들 수 있는 경우를 추가해서 더해준다. 

4의 경우를 보자. 1의 동전 4개일 때 /  2원 1개, 1원 2개 / 2원 2개의 3개의 케이스가 생긴다.

원래 표에 존재하던 1의 동전 4개일 때를 제외하고 2원 1개, 1원 2개 / 2원 2개를 보자.

2원을 빼고 생각해보면 1원 2개, 2원 1개가 된다. 이건 2의 경우의 수와 동일하다. 즉, 2일때의 경우의 수를 더해준다.

이를 이용해서 나머지 표를 채워보자.

1	2	3	4	5	6	7	8	9	10
1	1+1	1+1	1+1+1	1+1+1	1+1+1+1	1+1+1+1	1+1+1+1+1	1+1+1+1+1	1+1+1+1+1+1

1	2	3	4	5	6	7	8	9	10
1	2	2	3	3	4	4	5	5	6

 

마지막 5원 역시 5원을 최소로 넣을 수 있을 때가 5인데,

5의 경우 5원을 추가한 케이스 하나를 추가한다.

10원의 경우,  위와 동일한 방식으로 5원을 빼면 5를 만들때와 동일한 식을 가지게 될 것이므로 5일때의 경우의 수를 추가한다.

1	2	3	4	5	6	7	8	9	10
1	2	2	3	3+1	4	4	5	5	6+3+1

1	2	3	4	5	6	7	8	9	10
1	2	2	3	4	4	4	5	5	10

 

이를 점화식으로 정리해보면,

1. 첫 동전(2원을 넣을때는 2원일 경우, 5원을 넣을때는 5원의 경우)을 넣을 때는 그 동전을 넣으면 0이 되므로 1을 추가하는 것 말고는 경우의 수를 가지지 않으므로

dp[i]++

2. 이후에는 기존에 존재하던 경우에 더하여 동전을 빼고 난 후의 값의 경우의 수를 추가하므로 

dp[i] = dp[i] + dp[i-coin]

이 되겠다.

 

이를 코드로 적어보면

fun main(args: Array<String>) {
    question9084()
}

fun question9084() {
    val case = readln().toInt()

    for (i in 1..case) {
        val kindCount = readln().toInt()
        val kind = readln().split(" ").map { it.toInt() }
        val bill = readln().toInt()

        val dp = Array(bill + 1) { 0 }

		// 동전의 종류대로 넣어봄
        for (j in 0..<kindCount) {

            for (k in 1..bill) {
            	// 동전이 가격보다 커지면 동전을 뺄 수 있다.
                if(k - kind[j] > 0) {
                    dp[k] = dp[k] + dp[k - kind[j]]
                    // 동전이 가격과 같으면 +1 해줌 
                    // 어차피 동전 하나 빼도 0이라 경우의 수가 없으므로 그냥 왕동전 하나 경우의 수 1추가 해주는거.
                } else if(k - kind[j] == 0){
                    dp[k]++
                }

                //println("dp[$k] = ${dp[k]}")

            }

        }

        println(dp[bill])

    }
}

 

((우우 dp 너무 못한다 어떡하지))