[java]백준 2293번: 동전 1, 동적 계획법(dynamic programming) 알고리즘

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

2293번: 동전 1

 

---

 

동적 계획법(dynamic programming)

복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로 써
최종적으로 복잡한 문제의 답을 구하는 방법

동적 계획법의 원리와 구현 방식

① 큰 문제를 작은 문제로 나눌 수 있어야 한다.

② 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.

③ 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다. 이를 메모제이션(memoization) 기법이라고 한다.
④ 동적 계획법은 톱-다운 방식top-down과 바텀-업 bottom-up 방식으로 구현할 수 있다.

ex) 피보나치 수열 공식: D[N] = D[N-1] + D[N-2]    // N번째 수열= N-1번째 수열 + N-2번째 수열

동적 계획법의 핵심 이론
1. 동적 계획법으로 풀 수 있는지 확인
2. 점화식 세우기
3. 메모제이션 원리 이해하기
4. 톱-다운 구현 방식 이해하기
5. 바텀-업 구현 방식 이해하기

-> 더 안전한 방식은 바텀-업, 톱-다운 방식은 재귀 함수의 형태로 구현돼있기 때문에 재귀의 깊이가 매우 깊어질 경우 런타임 에러가 발생할 수 있다.

 

---

 

코드

 

import java.util.*;

public class j2293 {

	static ArrayList<ArrayList<Integer>> coins;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // n가지 종류의 동전
		int k = sc.nextInt(); // k원
		int[] coins = new int[n]; // n개의 동전의 가치

		for (int i = 0; i < n; i++) {
			coins[i] = sc.nextInt();
		}

		int[] DP = new int[k + 1]; // 0원부터 k원까지 가능한 경우의 수-> 구할 값은 value[k]

		// 첫번째 코인으로 먼저 value를 구해준다. 0의 중복을 피하기 위하여, 동전을 하나씩 비교하며 경우의 수 더해주기
		int first = coins[0];
		for (int i = 0; i <= k; i++) {
			if (i % first == 0) {
				DP[i]++;
			}
		}

		// 다음 동전부터 1~k번째 비교
		for (int i = 1; i < n; i++) {
			int cur = coins[i]; // 현재 비교할 코인
			for (int j = 1; j <= k; j++) { // j는 1~k원을 의미한다. 1원부터 하는 이유는 0은 모두가 0인 1개인데 위 첫번째 코인때 구해줬으므로
				if (j >= cur) { // 현재 코인을 넣어서 비교하려면 j원이 현재코인 cur보다 커야하므로
					// value[j](j원의 경우의 수)는 전까지의 코인으로 구했던 j까지의 경우의 수(value[j])에 현재 코인 넣었을
					// 때(value[j-cur) 더해주기
					// value[j-cur]의 이유: 현재코인 하나 넣어줬을 때는 j원에서 현재코인의 값 빼줬을 때 경우의 수이므로
					DP[j] = DP[j] + DP[j - cur];
				}
			}
		}

		System.out.println(DP[k]);

	}

}

 

 

풀이

 

int[] DP = new int[k + 1]; // 0원부터 k원까지 가능한 경우의 수-> 구할 값은 value[k]

 k원이 가능한 코인들의 경우의 수를 구하므로 DP []      // 0~k까지의 경우의 수를 구하자

 

 

예시에 1, 2, 5 가치의 코인들이 있다. 코인을 차례대로 DP []를 구해준다.

* 첫 번째 코인을 사용하여 DP []를 구한다. 0~k까지 코인으로 나누어 떨어지면(가능하므로) DP [i]++해준다. 

// 첫번째 코인으로 먼저 value를 구해준다. 0의 중복을 피하기 위하여, 동전을 하나씩 비교하며 경우의 수 더해주기
		int first = coins[0];
		for (int i = 0; i <= k; i++) {
			if (i % first == 0) {
				DP[i]++;
			}
		}

 

 

 

두 번째 코인부터 n번째 코인까지 차례대로 j: 1~k원까지 DP [j]를 구해준다. 

* 현재 코인 cur을  j: 1~k원까지 하나씩 넣어서 비교

  //  j가 1 원부터인 이유는 첫 번째 코인에서 0번째를 구해줬는데 0원이 되는 경우의 수는 모두가 0인 하나이므로 끝

	// 다음 동전부터 1~k번째 비교
		for (int i = 1; i < n; i++) {
			int cur = coins[i]; // 현재 비교할 코인
			for (int j = 1; j <= k; j++) { // j는 1~k원을 의미한다. 1원부터 하는 이유는 0은 모두가 0인 1개인데 위 첫번째 코인때 구해줬으므로
				if (j >= cur) { // 현재 코인을 넣어서 비교하려면 j원이 현재코인 cur보다 커야하므로
					// value[j](j원의 경우의 수)는 전까지의 코인으로 구했던 j까지의 경우의 수(value[j])에 현재 코인 넣었을
					// 때(value[j-cur) 더해주기
					// value[j-cur]의 이유: 현재코인 하나 넣어줬을 때는 j원에서 현재코인의 값 빼줬을 때 경우의 수이므로
					DP[j] = DP[j] + DP[j - cur];
				}
			}
		}

 

현재 코인: cur

 j: 1~k원이 cur보다 크거나 같아야지 동전을 넣어주므로 j>=cur 조건일 때 점화식을 사용한다.

 

점화식: D [j]=D [j]+D [j-cur]

 

전까지 구했던 j원까지의 경우의 수 D [j]에 * 현재 코인 cur을 j: 1~k원까지 하나씩 넣어서 비교할 것이므로 현재 코인을 하나 넣었을 때는 j-cur원이므로 j-cur원 가치 경우의 수 D [j-cur]을 더해준다. 

 

반복하면 끝!

 

 

 

 

출처: 백준, Do it! 알고리즘 코딩테스트 자바 편(김종관 지음)