[BaekJoon] 백준 9084번 동전

[BaekJoon] 백준 9084번 동전

 

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

 

내코드

 

- 조금 이해하기 어려운 DP문제였다. 나중에 다시 풀어봐야겠다.

- 점화식은 다음과 같다.

d[0] = 1;
for (i = 1; i <= n; i++) // 동전 종류만큼 반복문을 돈다.
    // 선택된 동전이 a[i]원짜리의 동전이면 a[i] ~ 목표금액 만큼 돌아서 bottom-up방식으로 푼다.
    for (j = a[i]; j <= m; j++)  
        // j원을 만들수 있는 가짓수 += (j - a[i])원을 만들수 있는 가짓수
	    d[j] += d[j - a[i]];

 

import java.util.Scanner;

public class test {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();

        while (T-- > 0) {
            // 초기화
            int N = sc.nextInt();
            int[] price = new int[N];
            for (int i=0; i < N; i++) {
                price[i] = sc.nextInt();
            }
            int goal = sc.nextInt();

            // 1 ~ goal 원을 만들기 위한 모든 방법의 수의 배열
            int[] result = new int[goal + 1];

            result[0] = 1;
            for (int i=1; i<= N; i++) {
                for (int j = price[i-1]; j <= goal; j++) {
                    result[j] += result[j - price[i-1]];
                }
            }

            System.out.println(result[goal]);
        }

        sc.close();
    }
}

 

참고

https://blog.naver.com/occidere/220793012348