n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//N, K 입력 받기
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
//코인 입력 받기
int[] coins=new int[n];
for (int i = 0; i < n; i++)
coins[i] = Integer.parseInt(br.readLine());
//각 동전에 대해서 현재 해당 금액을 만들 수 있는 경우의 수에 +해주기
int[] dp=new int[k+1];
for(int coin:coins){
if(coin>k)
continue;
dp[coin]+=1;
for(int i=1; i+coin<=k; i++)
dp[i+coin]+=dp[i];
}
System.out.println(dp[k]);
}
}
한 동전을 하나 사용하면 해당하는 금액을 만들 수 있는 경우의 수가 1 늘어난다. -> 어떤 금액을 만들 수 있을 때, 그 금액에 한 동전을 더한 금액을 만들 수 있는 경우의 수가 어떤 금액을 만들 수 있는 경우의 수만큼 늘어난다.
😁