[백준] 2293번 - 동전 1 (Java)

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

2293번: 동전 1

 

<문제 분석>

동전의 종류가 n개 있다. k원이 되도록 하는 경우의 수를 구해야 한다.

동전의 수는 제한이 없다.

시간제한이 0.5초 이므로 이분탐색 혹은 DP일 가능성이 높다.

 

<풀이>

배열을 사용해서 동전의 가치를 저장한다.

dp[i]는 i원까지 동전의 경우의 수이다.

10원을 표현하기 위해 동전 1, 2, 5를 갖고 있을 때 경우의 수는

점화식

dp[n] = dp[n-1] + dp[n-2] + dp[n-5]

 

<코드 구현>

import java.util.Scanner;


//[백준] 2293번 - 동전 1 (Java)

public class Main {
    static int n, k;
    static int coin[];
    static int dp[];
    
    public void InputData() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        coin = new int[n];
        dp = new int[k+1];
        for (int i=0; i<n; i++) {
            coin[i] = sc.nextInt();
        }
    }

	public void Solve() {
        dp[0] = 1;
        for (int i=0; i<n; i++) { // 돈 종류마다 반복문 수행 ex) 1 - 2 - 5 ...
            for (int j=coin[i]; j<=k; j++) {
                // 예제풀이 k = 10
                // dp[10] += dp[9]; 동전 1의 경우
                // dp[10] += dp[8]; 동전 2의 경우
                // dp[10] += dp[5]; 동전 5의 경우
                dp[j] = dp[j] + dp[j - coin[i]];
            }
        }
        System.out.println(dp[k]);
	}
    
	public static void main(String[] args)
	{
		Main m = new Main();
		m.InputData();
        m.Solve();
	}
}

 

<제출 결과>