BOJ) 동전 1

동전 1

2293번: 동전 1

풀이

 

n 가지 종류의 동전을 각각 여러개 이용해서 k원이 되게 하는 수를 구하는 문제다.

처음에는 dfs로 접근했다가, 동전은 몇개라도 사용할 수 있다는 조건을 보고 DP로 선회했다.

각각 동전에 대해서 K원 이하일 때, 쓰일 수 있는 모든 돈에 경우의 수를 추가시켜주었다.

 

for문을 돌면서 각 동전 coin에 대해coin의 가치부터 K원 까지 들어갈 수 있는 경우만 추가시켜주면 해결되는 문제였다.

 

코드

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[] coinArr = new int[n];
        for(int i=0; i<n; i++) {
            coinArr[i] = Integer.parseInt(br.readLine());
        }
        br.close();
        solution(n,k,coinArr);
    }

    private static void solution(int n, int k, int[] coinArr) {
        int[] dp = new int[k+1];
        dp[0] =1;
        for(int coin : coinArr) {
            for(int j=coin; j<=k; j++) {
                if(j-coin >=0) { dp[j] += dp[j - coin]; }
            }
        }
        
        System.out.println(dp[k]);
    }
}