[골드5] 2293. 동전 1(Java)

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

2293번: 동전 1

동전은 영어로 코인

---

※  문제를 요약하면 아래와 같습니다.

▶ N가지 종류의 동전이 주어졌을 때 가치의 합이 K가 되는 모든 경우의 수를 출력

▶ 각각의 동전은 몇 개라도 사용 가능

▶ Input : 첫째 줄에 N, K 그 다음줄에 N개의 동전의 가치가 입력

▶ Output : 첫째 줄에 경우의 수 출력

---

◈ Input - 1

3 10
1
2
5

◈ Output - 1

10

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ DP 규칙 탐색

    1. 값이 0일 경우 어떠한 동전도 사용하지 않는 경우의 수 1 존재

    2. DP의 규칙을 탐색해봐유~ (Input-1 활용)

        2-1. 1만 활용할 경우 0~10까지 만들 수 있는 경우의 수

       2-2. 1,2만 활용할 경우 0~10까지 만들 수 있는 경우의 수

       2-3. 1,2,5만 활용할 경우 0~10까지 만들 수 있는 경우의 수

       2-4. DP 결과

    3. 위 결과를 통해 어떠한 코인이 왔을 경우 DP[j] += DP[j-코인값]이 성립하는 것을 확인 할 수 있다.

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(bReader.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		int[] narrDP = new int[K + 1];
		int[] narrCoin = new int[N];

		for (int i = 0; i < N; i++) {
			narrCoin[i] = Integer.parseInt(bReader.readLine());
		}
		// 0일 경우 0개의 동전을 뽑는 경우의 수 1
		narrDP[0] = 1;
		int nMin = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			for (int j = narrCoin[i]; j <= K; j++) {
				narrDP[j] += narrDP[j - narrCoin[i]];
			}
		}

		bWriter.write(String.valueOf(narrDP[K]));

		bWriter.close();

	}
}

---

Good Luck! (피드백 감사합니다!)