[Project Euler] 31. 영국 화폐 액면가를 조합하는 방법의 수

31. 영국 화폐 액면가를 조합하는 방법의 수

영국의 화폐 단위는 파운드(£)와 펜스(p)이고, 동전의 종류는 아래와 같습니다.

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p)
이 동전들을 가지고 2파운드를 만드는 방법은 다양할 것입니다. 예를 하나 들면 이렇습니다.

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
2파운드를 만드는 서로 다른 방법은 모두 몇가지나 있습니까?

Click

http://blog.mycila.com/2009/06/project-euler-problem-31.html 블로그에서 본 방법이 단일 경우에 대해서는 최선의 방법일 듯하네요. 아래 공식을 이용한 방법인데.... 200 = 200*a + 100*b + 50*c + 20*d + 10*e + 5*f + 2*g + 1*h

<script language="Javascript" type="text/javascript">
function p31(){
  var count = 2; // for a = 1, a = 0 and b = 2`
  for (var b = 0; b <= 1; b++)
   for (var c = 0; 100 * b + 50 * c <= 200; c++)
    for (var d = 0; 100 * b + 50 * c + 20 * d <= 200; d++)
      for (var e = 0; 100 * b + 50 * c + 20 * d + 10 * e <= 200; e++)
        for (var f = 0; 100 * b + 50 * c + 20 * d + 10 * e + 5 * f <= 200; f++)
          for (var g = 0; 100 * b + 50 * c + 20 * d + 10 * e + 5 * f + 2 * g <= 200; g++)
            count++;
  return count;
}
</script>

하지만 개인적으로 단일 방법보다는 범용적인 방법을 더 좋아하므로 동적 계획법(Dynamic Programming)쪽에 더 점수를 주어봅니다.

동적계획(動的計劃, dynamic programming)은 어떤 알고리즘이 부분 문제 반복과 최적 기본 구조라는 특징을 가지고 있을 때, 이 알고리즘의 실행시간을 줄이는 방법이다. 수학자인 리처드 벨만이 1953년에 '동적계획'이라는 용어를 만들었다.

위키백과 : 동적계획법

제가 구현한 것은 동전의 종류, 배열, 원하는 n값에 모두 적용 되도록 구현해 봤습니다.

0원을 구하는 경우는 아무것도 선택하지 않는 1가지 방법 뿐.
1개의 동전으로 n원을 구할 수 있는 경우의 수는 1 or 0이다.
이때 동전 k가 하나 추가 되면, k가 없을 때의 경우의 수에 k를 하나 이상 선택한 경우의 수를 더해 주면 된다.
즉 새로운 newcnt[n] = oldcnt[n] + newcnt[n-k]가 된다.

이때 n-k가 n보다 클 경우. 역시 마찬가지로 k를 선택하지 않은 경우와 k를 하나 이상 선택한 경우를 더해야 한다.
이렇게 n-ak를 해 내려가면 n%k값에 도달하게 되고 이 수는 k값보다 작으므로 k를 선택하지 않은 oldcnt[n%k]와 동일한 값이라는 것을 알 수있다.
그렇다면 이걸 다시 역으로 타고 올라가면서 구하면 newcnt[n]값을 구할 수 있다.

같은 방법으로 동전을 추가해 나가면서 구하면 최종 값을 구할 수 있다.

위 방법을 효율적으로 하기위해 0~n까지 배열을 선언하여 1개의 동전 구할 수 있는 경우의 수로 초기화 한 후, 새로 동전을 추가 할때마다 새로운 동전의 가치 k부터 cnt[i] = cnt[i] + cnt[i-k]를 해나가면 원하는 수를 구할 수 있음.

<script language="Javascript" type="text/javascript">
function countCombineMoney(money,n){
    var cnt = new Array(); //i 값을 만들 수 있는 경우의 수.

    cnt[0] = 1; //0원을 만들 수 있는 경우의 수는 아무것도 선택하지 않은 1가지 경우뿐.
    for(var i=1; i<=n; i++) //동전 1개로 구할 수 있는 경우의 수는 1 or 0(불가)
        if(i%money[0] == 0)
            cnt[i] = 1;
        else
            cnt[i] = 0;
    
    var max = 0;
    for(var i=1; i<=money.length; i++)
        for(var j=money[i]; j<= n; j++)
            cnt[j] += cnt[j-money[i]];    //newcnt[n] = oldcnt[n] + newcnt[n-k]

    return cnt[n];
}
</script>