고등수학/고등수학(하)

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

한량 지아이 2020. 12. 4. 00:04
반응형

굉장히 유형화 되어 있지만

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

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

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

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

 

문제

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

 

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

중학교 1학년때 배운 약수의 개수 문제가 고등학교에서도 그대로 나옵니다. 다만, 총합이나 총곱 등 조금 더 다루는 내용이 많아지죠. 여러개 찾아볼 필요 없이, 오늘은 이 내용을 총정리 해드리

ladyang86.tistory.com

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

반응형