[백준] 9084번 동전

문제링크: 백준 9084번 동전

---

1. 아이디어

스스로 풀지 못해서 블로그를 돌아가며 풀이를 찾아 해멨지만, 이해하는데 2시간이나 걸렸다… 다들 천재들인가보다…

결국 이해한 내용을 풀어서 작성해본다.

• 기본 큰 개념

  1. 내가 n원짜리 가지고 목표금액 t원을 만든다고 한다면, (t-n)원의 경우에다가 n원짜리를 넣어주면 된다. 즉, (t-n)원을 만드는 경우가 된다.

  2. n원을 만드는 경우의 수가 m개라면 (t-n)원을 만드는 경우의 수 + m개가 된다.

• 예시1)

  1. 내가 2원짜리 가지고 4원을 만든다고 한다면, 2원의 경우에다가 2원짜리를 넣어주면 된다. 즉, 2원을 만드는 경우 + 1이 된다.

  2. 2원을 만드는 경우의 수는 1개이다. 정답은 1이 된다.

  3. 0원을 만드는 경우의 수는 무조건 1개로 가정해야 점화식이 성립한다.

• 예시2) 1, 2, 5원짜리로 5원을 만들어보자

  • 1원짜리로 1~5원을 만드는 경우의 수
    [1, 1, 1, 1, 1] -> 마지막 1이 정답
    -> 여기서 유추할 수 있는 점화식은 a(n) = a(n-1(1원)) (a(n)은 n번째 금액을 만드는 경우의 수)
    -> 여기서 a(1) = a(0)이 성립되어야 하므로 a(0) = 1로 가정한다.
    
  • 1원짜리로 만드는 경우의수에서 2원짜리를 추가해서 1~5원을 만들어보자
    [1, 1, 1, 1, 1] -> 기존 1원짜리로 만드는 경우의 수 배열
    [0, 1, 0, 1, 0] -> 2원짜리로 만드는 경우의 수 배열
    
  • 1원을 만들려면?
    기존 경우 1
    => [1]
    

  • 2원을 만들려면?
    기존 1원으로 2원을 만든 경우(1)
    + 기존 1원으로 0원을 만든경우(1)에 2원을 더해주는 경우
    = 2
    => [1, 2]
    

  • 3원을 만들려면?
    기존 1원으로 3원을 만든 경우(1)
    + 기존 1원으로 (3-2)인 1원을 만든 경우(1)에 2원을 더해주는 경우
    = 2
    => [1, 2, 2]
    
  • 4원을 만들려면?
    기존 1원으로 4원을 만든 경우(1)
    + 기존 (4-2)인 2원을 만든 경우(2)에 2원을 더해주는 경우
    = 3
    => [1, 2, 2, 3]
    

  • 5원을 만들려면?
    기존 1원으로 5원을 만든 경우(1)
    + 기존에 (5-2)인 3원을 만든 경우(2)에 2원을 더해주는 경우
    = 3
    => [1, 2, 2, 3, 3]
    

  • 정리하면, 기존 동전으로 만들었던 해당금액의 동전의 경우의 수
    + (해당금액 - 현재동전금액)인 값을 기존 동전으로 만들었던 경우
    

    => arr2[target] = arr1[target]+ arr2[target - coin]
    

    여기서 arr배열을 계속 만들지 않고 활용한다면 arr1을 dp배열로 바꿀 수 있음.
    (target - coin은 target보다 항상 뒤에 있기 때문에 dp배열을 계속 활용해도 됨)
    

    dp[target] = dp[target] + dp[target - coin]
    => dp[target] += dp[target - coin]

---

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

public class Main {
    static int coinKinds;
    static int[] coinValue;
    static int target;
    static ArrayList<Integer> answerList;
    static int[] dp;

    public static void solution() {
        dp = new int[target + 1];
        dp[0] = 1;

        for (int i = 0; i < coinValue.length; i++) {
            int curCoin = coinValue[i];
            for (int j = curCoin; j <= target; j++) {
                dp[j] += dp[j - curCoin];
            }
        }

        answerList.add(dp[target]);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        answerList = new ArrayList<>();
        int times = Integer.parseInt(st.nextToken());

        for (int i = 0; i < times; i++) {
            st = new StringTokenizer(br.readLine());
            coinKinds = Integer.parseInt(st.nextToken());
            coinValue = new int[coinKinds];

            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < coinKinds; j++) {
                coinValue[j] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine());
            target = Integer.parseInt(st.nextToken());

            solution();
        }

        for (int i = 0; i < answerList.size(); i++) {
            System.out.println(answerList.get(i));
        }
    }
}

• 학습내용

  • 기존 계산했던 내용을 활용하는 문제! Tabulation

  • 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정!!

---

마지막 수정일시: 2022-11-28 02:20