[2293] 동전1 - Java[자바]

 

 

| 문제 링크

 

 

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

2293번: 동전 1

 

 

 

 

 

---

 

 

 

 

| 문제

 

1. N개 종류의 동전으로 K 금액을 만들 수 있는 경우의 수를 구하시오.
   (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000)

 

 

 

 

---

 

 

 

 

| 풀이

 

1. DP 방식으로 문제를 풀었으며, 동전 하나(token1)를 기준으로(동전의 순서는 중요하지 않습니다) 1부터 K까지 금액별로 나올 수 있는 경우의 수를 배열(0번째 인덱스는 1로 설정)로 생성합니다.
2. 1번에서 만든 배열을 활용하여 다음 동전 하나(token2)를 추가 했을 때, token2의 값으로 나누어 떨어지는 배열의 인덱스 마다 값을 누적해서 더해줍니다.
3. 모든 동전에 대해서 2번 작업을 완료 후 k번째 인덱스에 있는 값(k가 나올 수 있는 경우의 수)을 출력해줍니다. 

 

 

 

 

---

 

 

 

 

| 코드

 

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		//동전의 종류를 배열로 입력받음
		int[] dp = new int[k+1];
		int[] tokens = new int[n+1];
        	//0번 인덱스를 1로 설정해 token 수 마다 경우의 수가 1씩 증가할 수 있도록 설정
		dp[0] = 1;
		for(int i = 1; i<=n; i++) {
			tokens[i] = Integer.parseInt(br.readLine());
            		//token만큼 뒤의 인덱스의 값을 누적시킴
			for(int j = tokens[i]; j<=k; j++) {
				dp[j] += dp[j-tokens[i]];
			}
		}
		
		System.out.println(dp[k]);
	}

}