Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

Posts List


2012년 3월 16일 금요일

[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>

댓글 없음:

댓글 쓰기