[백준, 2293] 동전 1

0. 문제 링크

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

2293번: 동전 1

---

1. 문제 핵심

1. DP 문제로 점화식을 찾는 것이 중요.

2. 4MB 제한이 있기 때문에 1차원 배열로 해결해야 함.

3. n가지 종류의 동전으로 k원을 만드는 경우의 수를 구해야 하지만 순서는 중요하지 않음.

 

---

2. 문제 접근

1. 점화식 감을 못잡아서 솔루션 봤음.
2. 1차원 DP 배열을 선언해서 차례대로 동전의 사용 가지 수를 계산 가능.
3. 크기가 1인 동전은 모든 경우에서 무조건 한 가지 조합을 만들 수 있음.
4. 크기가 N인 동전은 비용이 N일 때부터 경우의 수가 증가하기 시작.
5. 점화식은 dp[i] = dp[i] + dp[i - coin];

---

3. 내 코드 분석

 

---

4. 베스트 코드 리뷰

 

---

5. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 동전1 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int coin;
		int dp[] = new int[k+1];
		
		for(int i = 0; i < n; i++) {
			coin = Integer.parseInt(br.readLine());
			for(int j = 1; j <= k; j++) {
				// 만들 수 있는 금액에서 현재 동전 크기만큼 제외한 금액으로 만들 수 있는 경우의 수를 현재 배열에 저장
				if(j - coin > 0) {
					dp[j] = dp[j] + dp[j - coin];
				}
				// 해당 코인으로 만들 수 있는 최초의 경우의 수
				else if(j - coin == 0) {
					dp[j]++;
				}
			}
		}
		System.out.println(dp[k]);
	}
}