[JAVA]백준 2624번: 동전 바꿔주기

www.acmicpc.net/problem/2624

2624번: 동전 바꿔주기

1. 문제 설명

 

지폐의 금액 T와 동전의 가짓수 K, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 지폐를 동전으로 교환하는 방법의 가지 수를 구하는 문제이다.

 

2. 풀이

 

dp[x]= 현재 금액이 x일 때 동전으로 교환하는 방법의 가지 수

 

pi 금액의 가지수가 중복으로 포함되지 않도록 dp [x]에 대해 아직 pi 금액을 이용한 가짓수가 포함되지 않은 dp [x-ni*pi]의 값을 더했다.

 

3. 코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int target, num;


        target = Integer.parseInt(br.readLine());
        num = Integer.parseInt(br.readLine());

        int[][] list = new int[num][2];
        int[] dp = new int[target + 1];

        for (int x = 0; x < num; x++) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            list[x][0] = Integer.parseInt(st.nextToken());
            list[x][1] = Integer.parseInt(st.nextToken());
        }

        dp[0] = 1;

        for (int y = 0; y < num; y++) {

            int base = list[y][0];

            for (int x = target; x >= base; x--) {

                for (int w = 1; w <= list[y][1]; w++) {

                    if (x - base * w < 0) {
                        break;
                    }

                    dp[x] += dp[x - base * w];

                }
            }
        }


        bw.write(String.valueOf(dp[target]));
        bw.flush();
        bw.close();
        br.close();

    }



}