N 개 타입의 동전으로 어떠한 금액을 만드는 것과 관련된 문제이다.


여기서 몇 가지 문제를 생각할 수 있는데,


1. Frobenius coin problem

이 문제는 NP-hard 문제로, GCD(최대공약수)가 1인 N 개 타입의 동전으로 만들 수 없는,

가장 큰 수를 찾는 문제이다. 이 수를 Frobenius(프로베니우스) number 라 한다.

하지만 N이 1,2,3 일 때는 다항시간에 찾을 수 있는 공식이 나와있다.

더 자세

한 내용은 위키피디아 http://en.wikipedia.org/wiki/Coin_problem 참고.



2. N 개 타입의 동전으로 어떠한 금액을 만들 때, 가장 적은 수의 동전을 사용했을 때의 동전의 수.

(단 N >= 1 이고 N[1] = 1 )

요 문제는 Greedy 한 방법으로 풀어도 되지만, DP 방법으로 풀 수도 있다.




3. N 개 타입의 동전으로 어떠한 금액을 만들 때, 가능한 동전 조합의 경우의 수를 구하는 경우.

(단 N >= 1 이고 N[1] = 1 )

이 문제는 약간 어려웠던거 같다. 그냥 생각만으로는 잘 안되서,

아주 간단한 케이스를 가지고 종이에 적어가면서 확인했다.




조합의 수를 구하는 문제는 좀 헷갈리긴 했지만,

생각을 좀 해보고, 간단한 케이스를 확인해 보면서 찾을 수 있었다.

반응형

설정

트랙백

댓글

  • 익명 2015.03.19 02:15 답글 | 수정/삭제 | ADDR

    비밀댓글입니다

    • BlogIcon 아자 2015.03.31 13:11 신고 수정/삭제

      앗.. 그렇군요.. 지적 감사합니다.
      내용 수정하겠습니다.