[BOJ] 백준 2293 - 동전 1 풀이

1. 문제

https://www.acmicpc.net/problem/2293

2293번: 동전 1

2. 풀이 Point

<풀이 Point>

• dp[p] = r
  • p의 수를 만들 수 있는 경우의 수 r
• 1 동전만 썻을 때의 개수, 1과 2 동전을 썻을 때의 개수, 1과 2와 5 동전을 썻을 때의 개수를 행렬로 그린다.
• 2가 있는 row의 경우 1과 2를 사용해서 1을 만들 수 있는 경우의 수를 의미한다.
• 하지만 2를 사용해서 1을 만들 수 있는 경우는 없으므로 1로만 만들 수 있는 경우의 수가 그대로 내려간다.
• 그 후 1과 2를 사용해서 2를 만들 수 있는 방법의 수는 1로만 2를 만들 수 있는 방법의 수 + 1과 2로 0를 만들 수 있는 방법의 수이다.
• 이를 생각하고 5쪽을 보면 5를 사용해서 1부터 4까지를 만드는 방법은 없으므로 2까지 계산한 값이 그대로 들어간다.
• 예를 들어 1, 2, 5를 사용하여 8을 만드는 방법의 수를 보자.
• 이 경우는 1과 2로 8를 만들 수 있는 방법의 수 + 1,2,5를 사용해서 3까지 만든는 방법의 수이다.
• 이를 이용하면 아래 그림과 같은 점화식이 나온다.
  
  

3. Code

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

import org.omg.CORBA.INTERNAL;

public class Main {
	static int n;
	static int k;
	static int[] numArr;
	
    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	n = Integer.parseInt(st.nextToken());
    	k = Integer.parseInt(st.nextToken());
    	
    	/* 
    	  dp[k] = k를 만들기 위한 경우의 수 r
      	 */
    	numArr = new int[n];
    	for (int i = 0; i < n; i++) {
    		numArr[i] = Integer.parseInt(br.readLine());
    	}
    	
    	int[] dp = new int[k + 1];
    	dp[0] = 1;  // 0을 만드는 경우의 수는 0 하나 이므로 dp[0] = 1로 설정한다.
    	
    	// dp 로직
    	for (int i = 0; i < n; i++) {
    		for (int j = numArr[i]; j <= k; j++) {
    			dp[j] += dp[j - numArr[i]];
    		}
    	}
    	
    	bw.write(Integer.toString(dp[k]));
    	bw.flush();
    	bw.close();
    	br.close();
	}
}

4. 배운점

1. 점화식이 바로 떠오르지 않는다면 일단 시간이 걸리더라도 다 써보자.
2. dp가 이해가 안 될때 이 문제를 무조건 한번 보자
   
   
   

5. 점수

30/100