백준 9084 java : 배낭문제

기업 코딩테스트 문제에 항상 나오는 배낭문제이다. 주로 DP로 풀이된다. 자료구조와 함께 우선적으로 풀이하겠다.

import java.util.Scanner;
import java.util.Vector;

public class bj9084
{
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        int T, i, M;

        T = scanner.nextInt();
        for(i = 0; i < T; i++){
            Vector<Integer> coin = inputCoin();
            M = scanner.nextInt();
            System.out.println(findAnswer(coin, M));
        }

        scanner.close();
    }

    public static Vector inputCoin(){
        System.out.println("inputCoin()");

        Vector<Integer> coin = new Vector<>();
        int N;
        int i, price;

        N = scanner.nextInt();
        for(i = 0; i < N; i++){
            price = scanner.nextInt();
            coin.add(price);
        }

        return coin;
    }

    public static int findAnswer(Vector<Integer>coin, int M){
        System.out.println("findAnswer()");
        int [] price = new int[M+1];
        int i, j;

        //N가지 동전으로 금액 M을 만드는 모든 방법의 수
        for(i = 0; i < coin.size(); i++){
            for(j = 1; j <= M; j++){
                if(j - coin.get(i) > 0){
                    price[j] = price[j] + price[j - coin.get(i)];
                }
                else if(j - coin.get(i) == 0)
                {
                    price[j]++;
                }
                System.out.print(price[j] + " ");
            }
            System.out.println();
        }

        return price[M];
    }
}