백 준 - 2293

www.acmicpc.net/problem/2293

2293번: 동전 1

 

문제는 다음과 같습니다.

 

문제의 목표는 문제의 조건에 맞는 경우의 수가 얼마나 되는가에 대해서 구하는 것입니다.

 

여기에다가 시간 제한이 매우 적으니 메모리제이션을 활용해서 동적계획법으로 구현을 해보겠습니다.

방향은 다음과 같습니다.

 

정리하자면 각각의 코인을 이용해서 만들 수 있는 경우를 계산한는데 다음 코인의 경우를 파악할 때는 이전 경우에서 시작함으로써 코인들의 조합들도 알아서 따질 수 있도록 해줍니다.

 

전체적인 코드는 다음과 같습니다.

import java.util.*;

public class Main {
    
    //문제 2293

    public static void main(String[] args) {

        Scanner stdin = new Scanner(System.in);

        int n = stdin.nextInt();
        int k = stdin.nextInt();

        int[] arr = new int[n];

        for(int i = 0 ; i < n ; i++) {

            arr[i] = stdin.nextInt();
        }

        int[] D = new int[k+1];

        D[0] = 1;

        for(int i = 0 ; i < arr.length ; i++) {

            for (int j = 0 ; j < D.length - arr[i] ; j++) {

                D[arr[i] + j] += D[j];
            }
        }

        System.out.println(D[D.length-1]);
        
    }

}