[Gold-4] 2293번 | 동적계획법(DP) | 자바(Java)

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

 

 

해당 문제는 DP를 사용해 주어진 동전의 가치로 해당 금액(k)을 만들 수 있는 경우의 수를 구하는 문제이다.

문제 예제와 같이 3가지의 동전과 각각의 가치 1,2,5가 주어졌을 때

이 세 가지 종류의 동전으로 10을 만들 수 있는 가지수를 구하는 것이다.

 

 

• 1원 10개
• 1원 8개 + 2원 1개
• 1원 6개 + 2원 2개
• 1원 4개 + 2원 3개
• 1원 2개 + 2원 4개
• 2원 5개
• 1원 5개 + 5원 1개
• 1원 3개 + 2원 2개 + 5원 1개
• 1원 1개 + 2원 3개 + 5원 1개
• 5원 2개

쉽게 하나하나 구해보면 위와 같은 총 10가지의 경우의 수가 나오게 될 것이다.

 

이제 이 문제를 동적계획법(DP)로 풀이해보자.

우선, 동전의 가치를 저장할 정수형 배열을 만들어야한다.

 

int [] coins = new int [n];

        for(int i=0;i<n;i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

 

그럼 이제 해당 금액을 만들 수 있는 경우의 수를 저장할 배열 dp를 초기화한다.

즉, dp[0]이 의미하는 바는, 금액이 0원이 되는 경우의 수를 의미한다.

금액이 0원이 되는 경우의 수는 1로 초기화하면 되겠다.

 

그럼, 이제 이 dp를 업데이트하면서 각 동전마다 금액 coin부터 k까지 순회하며, dp[x] += dp[x-coin]를 수행하며 금액 x를 만드는 경우의 수를 저장하면 된다.

 

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));
        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]; //dp[x] : 금액 x를 만드는 경우의 수
        dp[0] = 1; //금액이 0원이 되는 경우는 1가지
        //dp[1] += dp[0] = 1
        //dp[2] += dp[1] = 1
        //dp[3] += dp[2] = 1
        //dp[4] += dp[3] = 1
        // ...
        //dp[10] += 1

        //coin=2

        //dp[2] += dp[0] = 2
        //dp[3] += dp[1] = 2
        //dp[4] += dp[2] = 3
        //

        for(int coin : coins) { // 1, 2, 5
            for(int x = coin; x<=k; x++) {
                dp[x] += dp[x-coin];
            }
        }

        System.out.println(dp[k]);

    }
}

 

 

coin의 역할 : 동전의 가치, coin이 특정 금액이라면, 그 금액부터 시작해 목표 금액까지 해당 동전을 사용해서 만들 수 있는 모든 금액을 살펴봄

dp[x] : 금액 x를 만들 수 있는 경우의 수, 이 값을 누적해서 업데이트

누적 과정 : dp[x] += dp[x-coin]

금액 x를 만들기 위해, coin이라는 동전을 추가로 사용한다면 이전에 x-coin 금액이 필요함

그래서 dp[x-coin]이 dp[x]에 더해지면서, 금액 x를 만들 수 있는 새로운 경우의 수가 추가되는 것임

---

 

위 코드를 아래 예시를 통해 이해하기 쉽게 설명하겠다.

 

1. coin = 1일 때:

• dp[1] += dp[0] → dp[1] = 1
• dp[2] += dp[1] → dp[2] = 1
• dp[3] += dp[2] → dp[3] = 1
• …
• dp[10] += dp[9] → dp[10] = 1

이 상태에서는 dp[x]가 모두 1이다. 이는 오직 1원짜리 동전만 사용한 경우를 의미한다.

하지만 이후에 coin = 2, coin = 5를 사용하여 dp 배열을 다시 갱신하면서 dp[x] 값이 증가하게 될 것이다.

 

2. coin = 2일 때:

• dp[2] += dp[0] → dp[2] = 2
• dp[3] += dp[1] → dp[3] = 2
• dp[4] += dp[2] → dp[4] = 3
• …
• dp[10] += dp[8] → dp[10] = 6

3. coin = 5일 때 :

• dp[5] += dp[0] → dp[5] = 4
• dp[6] += dp[1] → dp[6] = 5
• …
• dp[10] += dp[5] → dp[10] = 10