[백준/Swift] 3067: Coins | PS일지

문제

3067번: Coins

간단한 문제 요약

동전의 종류(1원, 5원, 10원, 50원 ...)가 주어질 때 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오!

 

문제 풀이

1,2,3원으로 6원 만드는 모든 경우의 수 구하는 방법

주어진 동전: 1,2,3

6원을 만드는 모든 방법을 구하는 방법을 어떻게 구할 수 있을까요?

 

1 + 1 + 1 + 3

1 + 2 + 3

3 + 3

 

...

6원보다 작은 3원 먼저 만들기 

 

우선 문제를 쪼개 6이 아닌 3을 구하는 방법으로는

1 + 1 + 1

1 + 2

3

3가지 경우가 있습니다.

 

1원을 만드는 방법은 1원을 사용하는 경우 한 가지.

2원을 만드는 방법은 1원을 사용했을 때, 2원을 사용했을 때 두 경우로 나눌 수 있습니다.

2원을 만들기 위해 1원 한 개를 사용했을 때 2 - 1 = 1. 그리고 1원을 만드는 모든 경우의 수는 1.

즉, 1원을 사용해 2원을 만들기 위한 방법은 1원 + 1원을 만드는 모든 경우의 수 1 => 1원을 만드는 모든 경우의 수 = 1입니다.

 

{ _ in

    예를들어 5원을 만들어야 하는데 동전 종류가 1원만 주어진다면 1+1+1+1+1 = 5. 한 가지가 존재합니다.
    5원 - 1원(1원짜리 동전을 사용) = 4원이 남는데 이를 만들 수 있는 모든 경우의 수는 1가지입니다.
    (1 + 1 + 1 +1 ) = 4원 ==  1가지

    4원을 만들 수 있는 경우는 1원을 사용할 경우 4 - 1 = 3원. 
    3원에서 1원을 더했을 때 4원. 그러니까 3원을 만들 수 있어야 합니다. 3원은 1+1+1 = 3. 1가지 입니다.
    .... 이런 방식입니다.
   
    즉, 5원을 만들기 위한 모든 경우의 수를 구하려고 할 때, 1원 한 개를 반드시 사용해야 한다면. 5-1=4원이 남는데,
    결국 4원을 만드는 모든 경우의 수의 값이 됩니다.
    4원을 만들기 위한 경우의 수 (1+1+1+1)에 반드시 사용해야 하는 1원 한 개를 붙여도
    한 가지( == 4원을 만들 수 있는 모든 경우의 수)가 되기 때문입니다. 
    여기서 포인트는 5원 - 원하는 동전 = 남은 동전(4원)이고 남은 동전을 만드는 최대 경우의 수는 곧 5원을 만드는 모든 방법임을 의미합니다.    

}()

 

다시 돌아와서 2원을 만드는 경우는 2원보다 작은 동전 1원, 2원을 사용해서 만들 수 있고, 1원을 사용했을 때는 2-1 ( 1원을 사용했다는 표현) = 1원. 1원을 만드는 모든 경우의 수가 존재하면 됩니다. 2 - 2 = 0.

 

0원을 만드는 방법?

 

0원을 가지고 아무것도 사용하지 않을 때 0원을 만들 수 있습니다. 1가지로 가정한다면 2 - 2 = 0 == 1가지가 됩니다.

1원을 사용해서 2원을 만드는 경우 + 2원을 사용했을 때 만들 수 있는 경우를 누적 합으로 메모제이션합니다.

 

 

3원을 만드는 방법은 3원보다 작거나 같은 동전인 1원, 2원, 3원 으로 만들 가능성이 있습니다.

1원을 사용할 경우

3 - 1 = 2원이 남는데 주어진 동전을 사용해서 2원을 만들 수 있다면!! 그 중 최대 경우의 수를 저장하고 있다면 해당 경우의 수 만큼 만들 수 있게 됩니다.

2원을 사용할 경우 3 - 2 = 1원이 남습니다. 주어진 동전을 사용해서 1원을 만들 수 있다면 그 최대 경우의 수는 결국 2원을 사용했을 때 3원을 만들 수 있는 경우의 수가 됩니다. 

3원을 사용할 경우 3 - 3 = 0. 1가지.

 

하지만 여기서 문제가 있습니다.

3 - 1 = 2원이 남는데 2원을 만드는 경우는 1원 + 1원. 2원 두 가지가 존재합니다. 각각의 경우에 1원을 더했을 때 2가지의 경우로 3원을 만들 수 있습니다. (1 + 1 + 1, 2 + 1)

3 - 2 = 1원이 남는데 1원 또한 1원을 사용해서 만들 수 있습니다. 2 + 1. 여기서 위의 경우와 중첩이 발생합니다...

 

 

한 가지 좋은 방법은 2원을 만들 때 주어진 동전 종류를 모두 사용해서 2원일 때 만들 수 있는 모든 경우를 누적 합산하고, 3원일 때 만들 수 있는 모든 방법을 구하고 .... 최종적인 동전 만드는 경우까지 증가시켜 나가는게 아니라. 가장 작은 동전을 사용해서 주어진 돈을 만들 때 까지 모든 경우를 구하고 그 다음 으로 큰 동전을 사용해서 이전에 구했던 작은 동전일 때 구했던 경우를 누적으로 더해가는 방식 입니다.

 

 

아래의 표는 dp입니다. money+1만큼의 배열을 통해 특정 돈을 만들 수 있는 경우의 수를 저장합니다.

동전/머니	0	1	2	3	4	5	6
1원	0	0	0	0	0	0	0

6원을 구할 때

1원을 사용해서 6원을 구하는 방법.

 

머니 1을 구할 때, dp[1-1] == dp[0]. dp[0]은 0원을 사용해 0원을 만드는 방법 1가지로 정의합니다.

동전/머니	0	1	2	3	4	5	6
1원	0	1

 

dp[1] = 1.

dp[1원을 만들 수 있는 경우는] = 한가지.

머니 2를 구할 때 dp[2 - 1] = dp[1] = 1

dp[2- 1 == 1] = dp[1]은 1원을 만들 수 있는 모든 경우의 수입니다. 위에서 구한 1가지 입니다. ( 1 + 1) 한 가지 .

dp[3- 1 == 2] = dp[2]는 1원을 사용했을 때 이전에 구한 2원을 사용하는 모든 경우의 수를 저장합니다. dp[3] += dp[2] == 1가지.

....

dp[6] += dp[5]  // 6원을 만들기 위해 1원을 사용했을 때 5원이 남는데 5원을 구할 수 있는 모든 경우의 수 == dp[6]이 됩니다.

동전/머니	0	1	2	3	4	5	6
1원	0	1	1	1	1	1	1

 

동전 2원을 사용했을 때 6원을 구하는 방법

동전/머니	0	1	2	3	4	5	6
1원	0(x)	1	1	1	1	1	1
2원	0(x)	0(만들 수 x)

동전 2원을 만들때의 경우.

dp[2] = dp[2-0](2원을 사용했을 때 경우의 수 1가지) + dp[2](이전에 2원을 만들 때 모든 경우 == 1원을 2개 사용한 1가지 경우) = 2.

dp[3] = dp[3-2] + dp[3] // 2원을 사용했을 때 1원을 만들 수 있는 최대 경우dp[1] =1. 2원을 사용하기 이전에 구했던(0원과 1원) 동전들로 3원을 만들 때 최대 경우의 수. = 1. dp[3] = 2.

dp[4] = dp[4-2] + dp[4] == 2 + 1 = 3. 

...

동전/머니	0	1	2	3	4	5	6
1원	0(x)	1	1	1	1	1	1
2원	0(x)	0(만들 수 x)	2	2	3	3	4

 

동전 3원을 사용했을 때 6원을 구하는 방법

다시 1원부터 6원까지, 3원을 사용해서 만들 수 있는 경우를 구합니다. 마찬가지로 3보다 작은 동전 1,2를 사용해서 경우의 수를 구했었는데 3원을 사용했을 때 남은 돈이 있다면 1,2원을 사용했을 때 구한 경우의 수를 이용할 수 있습니다.

 

dp[3(3원을 만드는 모든 경우의 수)] = dp[3(이전 1,2원을 통해 구했던 3원을 만드는 방법==2)] + dp[3-3(3원을 사용했을 때 0원 == 1가지)] = 3.

dp[4(4원을 만드는 모든 경우의 수)] = dp[4(3원 사용하기전 1,2원을 통해 구했던 4원을 만드는 방법==3. 이때 3원을 사용하지 않았기에 중첩될 경우 전혀 없다!!)] + dp[4-3(3원을 사용했을 때 1원이 남는데 1원을 만들 수 있는 모든 경우의 수 == 1)] = 4

dp[5]  = dp[5]+dp[5-3] = 3+2 = 5

dp[6] = dp[6]+dp[6-3] = 4+3 = 7.

동전/머니	0	1	2	3	4	5	6
1,2원 사용했을 때	0	1	2	2	3	3	4

3원을 사용했을 때

동전/머니	0	1	2	3	4	5	6
3원	0	1	2	2 + 1	3 + 1	3 + 2	4 + 3

n == 만들고자 하는 금액.

점화식으로 dp[n] = dp[n-사용할 동전] + dp[n] 

그리고 정답은 dp[n]이 답이 됩니다.

코드

var res = ""
(0..<Int(readLine()!)!).map{ _ in
    _=readLine()
    // 동전 종류.
    let coins = readLine()!.split{$0==" "}.map{Int(String($0))!}
    // 만들어야 할 최종 금액.
    let targetMoney = Int(readLine()!)!
    // 작은 동전부터 큰 동전까지. 각각의 동전을 사용할 때 특정 금액을 구할 수 있는 모든 경우를 누적해 나갑니다.
    var dp = Array(repeating: 0, count: targetMoney+1); dp[0] = 1
    // 작은 동전부터 큰 동전까지. 각각의 동전은 '$0'으로 받습니다.
    coins.map{
	    //특정 동전이 특정 금액을 만들 수 있는가? 있다면 dp에 값을 갱신해나갑니다.
        for money in ($0...targetMoney) {
            dp[money] += dp[money-$0]
        }
    }
    res += "\(dp[targetMoney])\n"
}
print(res)