[고2]확통

[레드향기]

풀이가 이해가 안가는데 다시 설명해주실 분 계신가요?

[성지훈]

지불 방법의 수에서는 100원을 낼 때 50원짜리 두개를 내는 것과 100원짜리 1개를 내는 것은 다른 방법이므로 다른 경우로 취급하고 지불 금액의 수에서는 이 두가지 경우 모두 100원이란 금액을 지불한 것이므로 같은 경우로 취급합니다.
지불방법.
50원짜리 3개, 100원짜리 2개 500원짜리 4개
50원짜리를 지불하는 방법은 0개~3개 의 4가지 경우가 있고
이 4가지 경우 각각에 대해서 100원짜리를 지불하는 방법은 0개~2개 의 3가지 경우가 있으므로 12가지가 되고,
이 12가지 경우 각각에 대해서 500원짜리를 지불하는 방법은 0개~4개 의 5가지 경우가 있으므로 60가지가 됩니다.
여기서 세가지 동전 모두 0개인 1가지를 제외해서 59가지.

[성지훈]

지불금액.
지불한 방법 중 지불된 금액이 같은 경우는 한 가지로 취급한다는 뜻입니다. 그래서 이 경우는 큰 단위의 금액을 쪼개서 생각하는데 무조건 쪼개는 것이 아니라 작은 단위의 금액을 모두 표현할 수 있을 때 쪼갭니다.
예를 들어 10원짜리가 4개 있고 50원짜리가 2개 있다면 총 140원인데 이 동전들로 10원~140원까지 10원단위의 금액을 모두 지불할 수 있습니다. 이럴 때는 50원을 10원짜리 5개로 생각해서 10원짜리 14개로 지불하는 금액의 수를 구하면 되겠죠. 그런데 만약 10원짜리가 3개있고 50원짜리가 2개 있다면? 이 때도 50원짜리를 쪼개서 생각해버리면 오류가 생깁니다. 40원,90원은 불가능했는데 가능해져버리니까요.

[성지훈]

성지훈 따져봐야 할 것은 더 작은 단위의 금액들을 모두 지불가능할 때 큰 단위의 금액을 한단계 아래 금액으로 쪼개서 생각한다는 것입니다. 지금처럼 50원짜리가 3개 100원짜리가 2개있는 상황에서는 이것들을 사용해서 500원 아래의 100원 단위(100,200,300,400)중 400원을 지불할 수 없으므로 500원은 100원짜리로 쪼개면 안됩니다. 반면 50원짜리 3개가 있으면 100원 아래의 50원 단위(50)를 모두 지불할 수 있으므로 100원짜리 하나는 50원짜리 2개인 것으로 취급합니다.
50원 3개, 100원 2개, 500원 4개로 지불하는 금액의 수
=50원 7개, 500원 4개로 지불하는 방법의 수
=8*5-1=39.
금액끼리 중복되지 않도록 변형해 주는 것입니다.

[레드향기]

성지훈 대단히 감사합니다!! 선생님 짱이십니다^^