[경우의 수] 동전문제 지불금액, 지불방법의 수

굉장히 유형화 되어 있지만

이해가 잘 안 가는 문제들이 몇개 있죠.

오늘은 경우의 수에서, 동전/혹은 지폐를

세는 문제를 좀 다뤄볼까 합니다.

간단하게 예제 하나만 다루면서 설명 해볼게요.

 

문제

100원짜리 동전 1개, 50원짜리 동전 3개, 10원짜리 동전 2개가 있다.

이 동전의 일부 또는 전부를 사용하여

지불할 수 있는 방법의 수를 a,

지불할 수 있는 금액의 수를 b라 할 때,

a-b의 값은?

(단, 0원을 지불하는 경우는 제외한다.)

 

1. 지불 할 수 있는 방법

어떤 동전을 몇 개 사용하느냐?

이게 포인트입니다.

 

같은 백원을 지불하더라도,

100원짜리 동전을 하나 쓰는 거랑,

50원짜리 동전을 두 개 쓰는 건 다르니까요.

 

이 부분은 양의 약수의 개수 세는 방법과

거의 같습니다.

 

100원/50원/10원짜리를 고르는 방법을

다 결정해줘야 지불 방법이 정해지겠죠?

 

곱의 법칙을 사용합니다.

2 x 4 x 3=24개네요.

 

0원을 지불하는 경우는 제외해야 하므로

구하는 방법의 수는 23개가 됩니다.

2. 지불 할 수 있는 금액

금액의 경우에는, 지불 방법과 다릅니다.

10원짜리는 쓰이는 개수가

금액을 유일하게 결정하죠.

1개 쓰면 10원, 2개 쓰면 20원..

 

그렇지만, 50원 짜리는 2개 사용하면 100원이므로,

100원짜리 1개와 지불할 수 있는 금액이 같죠.

100원 : 100 x 1

100원 : 50 x 2

둘 다 100원이기 때문에 한 번만 세야 합니다.

 

이럴 때는 복잡하게 100원, 50원짜리 섞어쓰지말고,

단위가 큰 100원짜리를 50원짜리로 환전해줍니다.

어차피 100원짜리 1개와

50원짜리 3개로 만들수 있는 금액은 250원인데,

50원짜리 동전 5개를 사용하면,

동전을 사용하는 갯수 = 금액이니까요.

 

 환전 후에는 위와 동일한 방법으로,

해당 동전으로 지불하는 방법을 세면 됩니다.

 

여기서는 50원짜리 5개, 10원짜리 2개이므로,

(5+1) x (2+1) - 1 = 18-1=17이죠.

(마찬가지로 0원을 지불하는 경우

1가지는 제외해줍니다.)

---

마지막으로 지불 방법과 지불 금액

알고리즘을 한 번 정리 해볼까요?

지불 방법 & 지불 금액 총 정리
지불방법	어떤 동전을 몇 개 사용하느냐에 따라 지불방법은 모두 다릅니다.   지불방법 = (동전①의 개수 + 1)(동전②의 개수 + 1)..(동전ⓝ의 개수 + 1) 화폐를 사용하지 않는 경우까지 포함하여 +1을 한 다음 곱한다.
지불금액	1. 동전의 단위가 작은 경우, 합쳐서 위의 금액을 만들 수 있는지 체크한다. ex) 50원짜리가 3개 있으면 100원을 만들 수 있다.   2. 작은 단위로 환전한다. ex2) 100원짜리 한 개를 50원짜리 두 개로 환전 한다.   3. 작은 단위의 동전으로 지불 방법을 센다. ex3) 50원짜리 5개로 만들 수 있는 금액을 센다.

방식이 이전에 포스팅 했었던,

양의 약수의 개수 구하는 방법과 동일하므로

같이 보시면 좋을 듯 하여,

링크 걸어둡니다.^^

 

ladyang86.tistory.com/68

[경우의 수] 양의 약수의 개수와 총합, 곱까지 총정리

그럼 다음에도 좋은 포스팅 갖고 올게요.