굉장히 유형화 되어 있지만
이해가 잘 안 가는 문제들이 몇개 있죠.
오늘은 경우의 수에서, 동전/혹은 지폐를
세는 문제를 좀 다뤄볼까 합니다.
간단하게 예제 하나만 다루면서 설명 해볼게요.
문제
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개로 만들 수 있는 금액을 센다.
|
방식이 이전에 포스팅 했었던,
양의 약수의 개수 구하는 방법과 동일하므로
같이 보시면 좋을 듯 하여,
링크 걸어둡니다.^^
그럼 다음에도 좋은 포스팅 갖고 올게요.
'고등수학 > 고등수학(하)' 카테고리의 다른 글
유리함수 절댓값 그래프 그리기 (0) | 2020.12.10 |
---|---|
[경우의 수] 시험 꿀팁 교란순열 (완전순열) (0) | 2020.12.05 |
[경우의 수] 양의 약수의 개수와 총합, 곱까지 총정리 (0) | 2020.11.27 |
산술기하 평균(부등식) - 기하적인 방법으로 증명하기 (0) | 2020.11.24 |
[귀류법] 루트2가 무리수임을 증명. 무조건 이해되는 설명. (0) | 2020.11.14 |