[백준] 2293번 동전 1 - Java

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

2293번: 동전 1

---

문제

---

코드

맞았습니다가 뜬 코드입니다. - 메모리 14128KB | 시간 140ms | 코드 길이 793B

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

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		int[] coin = new int[n];
		int[] dp = new int[k + 1];
		
		dp[0] = 1;
		
		for(int i = 0 ; i < n ; i++) {
			coin[i] = Integer.parseInt(bf.readLine());
			for(int j = coin[i] ; j <= k ; j++) {
				dp[j] += dp[j - coin[i]];
			}
		}
		
		bw.write(Integer.toString(dp[k]));
		
		bw.flush();
		bf.close();
		bw.close();
	}
}

다이나믹 프로그래밍을 이용한 코드입니다.

coin 배열에는 종류별 동전의 액수가 들어있고 dp 배열은 인덱스에는 금액이, 해당 인덱스의 요소로는 경우의 수가 들어있습니다. dp배열의 인덱스가 금액을 나타내는 이유는 이전 인덱스의 요소, 즉 경우의 수를 이용하여 다음 인덱스의 경우의 수를 구하고, 또 다음 인덱스의 경우의 수를 구하여 결과적으로는 k원의 경우의 수를 구하기 위해서 입니다.

 

만약 j원의 경우의 수를 알고싶다면, j원에서 coin[i]원을 뺀 인덱스의 경우의 수를 확인하여 갱신해줍니다.

coin[i]원을 이용하여 j원을 채우기 위해서는 coin[i]원을 이미 사용했다치고, 남는 돈인 j - coin[i] 원을 채울 경우의 수를 생각하면 되기 때문입니다. 그리고 그 경우의 수는 coin[i]의 i번째 실행부터 갱신되어가고 있기 때문에 경우의 수를 누적하여 생각할 수 있습니다.

coin[i]는 해당 가격부터 들어갈 수 있기 때문에 (2원이라면 2원부터 넣을 수 있음) 두번째 반복문 j는 coin[i]원 부터 시작하도록 했습니다.

 

---

후기

경우의 수를 다 생각해보다가 결국에는 찾아봤습니다 ;; 다이나믹 프로그래밍은 생각은 어려운데 정답 알고리즘은 체계적이어서 풀이를 보거나 풀면 희열이 느껴진다고 해야하나 싹 내려가는 기분이라 좋아합니다.