UVA 674_Coin Change

2469 단어

제목:


숫자를 정해서 1, 5, 10, 25, 50의 조합 방식이 얼마나 되는지 구하세요.

분석:


단순 계수 dp, dp[i][j]는 전 i+1개의 원소로 구성된 j의 종수를 나타낸다. dp[i][0]를 1로 초기화하는 것은 원소를 선택하지 않는 방법이 항상 있기 때문이다.

코드:

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 7500;
long long dp[10][maxn + 5];
int main (void)
{
    int a[5]={1,5,10,25,50};
    int n;
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i <=5; i++) dp[i][0] = 1;
    for(int i = 0; i < 5; i++){
        for(int j = 1; j < maxn; j++){
                if(j-a[i]>=0){
                    dp[i+1][j] = dp[i][j]+dp[i+1][j-a[i]];
                }else
                    dp[i+1][j] = dp[i][j];
            }
        }
    while(cin>>n){
      cout<<dp[5][n]<<endl;
    }
}

좋은 웹페이지 즐겨찾기