[백준 2293] 동전 1

문제 출처

1. 구상

• 동전의 가치를 1차원 배열에 저장

• 1 ~ 가치의 합까지 경우의 수를 1차원 배열에 저장
  알고리즘 출처
  
  

2. 구현

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

public  class Main {
	
	public static int[] cas; 
	public static int[] rec;	
	
	public static void main(String[] args) throws Exception {
		Scanner s = new Scanner(System.in);	
		
		int num = s.nextInt();
		int total = s.nextInt();
		
		//동전의 가치 저장
		cas = new int[num + 1];	
		//각 총액마다의 가지수 저장
		rec = new int[total + 1];
		
		rec[0] = 1;
		
		for (int i = 1; i <= num; i++) {
        	//동전의 가치 입력
			cas[i] = s.nextInt();
            //동전의 가치로 동전의 가치부터 총액까지의 경우의 수 구하기
			for (int j = cas[i]; j <= total; j++)
				rec[j] += rec[j - cas[i]];
		}
			
		
		System.out.println(rec[total]);	
				
	}
	
} 

- (총액 + 1) 크기의 배열을 만들어서 경우의 수를 저장해서 이용.

- 입력받은 가치로 만들 수 있는 경우의 수를 1 ~ 총액까지 계산.

- 경우의 수를 계산할 때 기존의 경우의 수를 이용하여 계산.