백준 (BOJ) 9084 동전 java dp

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

9084번: 동전

 

 

동전 관련 dp의 대표적인 동전 문제 (?)

 

한 번 깔끔하게 짚고 넘어가면 좋을 것 같다.

 

Bottom up 방식으로 하나씩 코인을 뽑아서 경우의 수를 더해 간다고 생각하면 된다.

 

개인적으로 Top down으로 접근하는 게 조금 더 복잡하다고 생각한다.

 

 

 

< 구현에 대한 핵심 아이디어 >

 

j값      i값        :        j는 만들려는 값, i는 지금 꺼낸 코인 값이다. 바로 아래는 '2원'과 '3원' 뽑은 경우이다.

↓        ↓

1원 = 2원 + (-1원)    →  의미 없음       

2원 = 2원 + 0원        →   dp[j] += dp[j - 2원 == 0원]  →  dp[2] += dp[2-2]  →  dp[2] += dp[0]

3원 = 2원 + 1원        →   dp[j] += dp[j - 2원 == 1원]  →  dp[3] += dp[3-2]  →  dp[3] += dp[1]

4원 = 2원 + 2원        →   dp[j] += dp[j - 2원 == 2원]  →  dp[4] += dp[4-2]  →  dp[4] += dp[2]

5원 = 2원 + 3원        →   dp[j] += dp[j - 2원 == 3원]  →  dp[5] += dp[5-2]  →  dp[5] += dp[3]  

6원 = 2원 + 4원        →   dp[j] += dp[j - 2원 == 4원]  →  dp[6] += dp[6-2]  →  dp[6] += dp[4]

...

 

3원 = 3원 + 0원        →   dp[j] += dp[j - 3원 == 0원]  →  d[3] += dp[0]

4원 = 3원 + 1원        →   dp[j] += dp[j - 3원 == 1원]  →  d[4] += dp[1]

5원 = 3원 + 2원        →   dp[j] += dp[j - 3원 == 2원]  →  d[5] += dp[2]

6원 = 3원 + 3원        →   dp[j] += dp[j - 3원 == 3원]  →  d[6] += dp[3]

...

 

이런 식으로 가면 결국

 

dp[만들려는 값] += dp[만들려는 값 - 지금 꺼낸 코인 값]이 된다.

 

 

 

다시 더 넓게 펼쳐서 보자.

 

1, 2, 3, 4, 5라는 동전을 가지고 있다고 할 때, 하나의 돈을 만들기 위해 더해지는 모든 경우의 수를 보면 다음과 같다.

 

...

dp[4] += (dp[4-1] + dp[4-2] + dp[4-3] + dp[4-4] + dp[4-5])   // 만들려는 값 보다 꺼낸 코인 값이 크면 안 된다.

dp[5] += (dp[5-1] + dp[5-2] + dp[5-3] + dp[5-4] + dp[5-5])

...

 

이런 방식으로 결국에는 만들려는 값에 대한 모든 경우의 수가 더해지게 된다.

 

 

 

요지는 위와 같이 특정 금액 1원, 2원, 3원... n원을 꺼냈을 때,

 

남은 금액(만들려는 값 - 지금 꺼낸 코인 값)만큼의 경우의 수만 더하면 만들려는 값에 대한 경우의 수가 완성되어 간다는 점인데,

 

남은 금액에 대한 경우를 dp[남은 금액 → 만들려는 값 - 지금 꺼낸 코인 값]에서 저장하고 있기에 가능하다는 점이다.

 

 

 

항상 느끼는 거지만 몇 줄 없는 dp의 간단한 구현은 기묘한 느낌을 준다.

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;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for(int t=0; t<T; ++t){
            int N = Integer.parseInt(br.readLine());
            int[] coins = new int[N];
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<N; ++i){
                coins[i] = Integer.parseInt(st.nextToken());
            }

            int M = Integer.parseInt(br.readLine()); // 목표 금액

            long[] dp = new long[M+1];
            dp[0] = 1;
            for(int coin : coins){
                for(int i=coin; i<=M; ++i){
                    dp[i] += dp[i - coin];
                }
            }

            sb.append(dp[M]).append("\n");

        }

        System.out.print(sb);
    }
}

 

 

 

시리즈물로 동전 바꾸기 https://verycrazy.tistory.com/130가 있다.

백준 (BOJ) 2624 동전 바꾸기 java dp