[ BOJ 백준 2624번 - 동전 바꿔주기 ] 해설 및 코드

https://www.acmicpc.net/problem/2624

 

목적

입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수를 구하자.

 

접근법

1. 2개의 배열을 이용해서 i번째 동전 n개로 만들 수 있는 금액 별 경우의 수를 계속 갱신해 나간다. 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
int T,k,p,n,s[2][10001];
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>T>>k;
    s[0][0]=1;
    while(k--){
        cin>>p>>n;
        f(i,0,T)if(s[0][i])f(j,1,n){
            int tmp=i+j*p;
            if(tmp>T)break;
            s[1][tmp]+=s[0][i];
        }
        f(i,0,T)s[0][i]+=s[1][i],s[1][i]=0;
    }
    cout<<s[0][T];
    return 0;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.