[BOJ 2293번] 동전 1(JAVA)

www.acmicpc.net/problem/2293

2293번: 동전 1

import java.io.*;
import java.util.*;

class Main{
   
   static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
   static StringBuilder sb=new StringBuilder();
   
   public static void main(String args[]) throws Exception {
//	   String s[]=br.readLine().split(" ");
//	   int N=Integer.parseInt(s[0]);
//	   int K=Integer.parseInt(s[1]);
	   Scanner sc=new Scanner(System.in);
	   int N=sc.nextInt();
	   int K=sc.nextInt();
	   
	   int[] arr=new int[K+1];
	   int coin[]=new int[N];
	   for(int i=0;i<N;i++) {
		   coin[i]=sc.nextInt();
	   }
	   arr[0]=1;
	   for(int i=0;i<N;i++) {
		   for(int j=1;j<=K;j++) {
			   if(j>=coin[i])	arr[j]+=arr[j-coin[i]];
		   }
	   }
	   System.out.println(arr[K]);
	   
   }
}

 이 문제는 아래 블로그 링크를 참고하여 풀어보았습니다.

extracold.tistory.com/5

백준 2293 : 동전 1

이 문제의 포인트는 아래 식입니다.

i원을 만드는 방법의 수=i-1원을 만드는 방법의 수+1원을 만드는 방법의 수

                             +i-2원을 만드는 방법의 수+2원을 만드는 방법의 수

                            ...+i-n원을 만드는 방법의 수+n원을 만드는 방법의 수 

이 식을 구현한 것이 위 코드의 arr[j]+=arr[j-coin[j]]입니다.

방법들을 모두 더해서 arr[K]에는 K원을 만드는 경우의 수가 저장되게 됩니다.