| [ QuizWit ] in KIDS 글 쓴 이(By): earny (O___L_) 날 짜 (Date): 2003년 12월 10일 수요일 오후 10시 57분 56초 제 목(Title): Re: [문제] 1999 루블 심심해서 위에서 OutSider 님이 생략한 자세한 설명을 달아봅니다. -_-;; 일단 고객과 점원이 가진 동전을 각자 최대한 큰단위의 동전으로 만든다고 생각을 합니다. 예를 들면 점원이 1원짜리 동전 8개가 있다면 5개를 고무줄로 묶어서 5원짜리 동전으로 생각하고 이렇게 만들어진 5원짜리 동전들을 또 최대한 고무줄로 묶어서 10원짜리 동전을 만들고.. 이런식으로 계속해서 최대한 큰 단위의 동전을 만듭니다. 고객도 마찬가지로 이렇게 합니다. 그러고 나서 점원과 고객이 각자 가지고 있는 동전의 개수를 종류별로 세어봅니다. 일단 1000원짜리 동전의 개수를 세어보면 돈의 합이 1999 원이므로 둘중 한명은 1000원 이상의 돈을 가지고 있을것이고 이 경우 동전을 묶어서 1000원짜리 동전 1개를 반드시 만들 수 있습니다. 따라서 1000원짜리 동전을 제외하고 다시 500원짜리 동전의 개수를 세어보면 둘의 돈의 합이 999 원이므로 둘중 한명은 반드시 500원 이상의 돈을 가지고 있을 것이므로 또 500원짜리 동전 1개를 만들 수 있습니다. 이제 남은 돈 499 원으로 100원짜리 동전의 개수를 세어보면 한쪽이 xyz 원의 돈이 있으면 나머지는 반드시 (4-x)y'z' 의 돈이 있게 되므로 각자 100원짜리 동전 x개와 4-x개를 가지므로 결국 100원짜리 동전은 합쳐서 4개 입니다. 비슷한 방식으로 계속 해나가면 50원짜리 동전은 1개 10원자리 동전은 4개 5원짜리 동전은 1개 1원짜리 동전은 4개 를 만들 수 있습니다. 결과적으로 정리하면 1000: 1 500: 1 100: 4 50: 1 10: 4 5: 1 1: 4 이렇게 됩니다. 이 동전으로 만들수 있는 조합의 개수는 2*2*5*2*5*2*5 = 2000 개이고, 이들 조합은 모두 서로 다른 값을 만들어 내므로 0 ~ 1999 원까지의 돈을 모두 만들어 낼 수 있습니다. 이제 고객이 a 원의 고양이 값을 계산하는 방식은 다음과 같습니다. 먼저 고객이 자신의 돈을 모두 점원에게 줍니다. 그러면 점원은 이제 앞에서 말한 동전을 모두 가지게 되므로 0~1999원까지 돈을 모두 만들어 낼수 있습니다. 따라서 점원은 고객에게 x-a원 즉, 고객의 원래돈에서 고양이 값을 뺀돈을 고객에게 돌려 줄 수 있습니다. |