동적계획법_2294_동전2

동적계획법

주어진 문제를 여러 부분 문제들로 나누어 푼 다음, 그 결과들로 큰 문제를 푸는 알고리즘 
어떤 문제를 풀기 위해 해결해야 하는 부분 문제의 개수가 k개라고 한다면, 전체적으로 풀어야하는 문제의 개수는 O(kN)개가 될 것이다. 이때 k가 충분히 무시할 수 있을 정도로  작은 수이고, 각가의 문제를 푸는데 걸리는 시간이 O(1)이라면, 문제의 결과를 저장할 O(N)의 메모리가 필요하며, O(N)만큼의  시간이 소요된다.

분할 정복 vs DP
분할하는 점은 동일하지만 전자는 겹치는 부분문제가 없지만, 후자는 있다는 것이다. 따라서 메모이제이션 기법으로 비효율적인 반복 연산을 줄인다. 

Greedy vs DP 
모든 경우를 메모리까지 소비해가며 샅샅이 체크하는 점에서 전자보다 후자가 실행 시간은 길지만, 근사치가 아닌 정확한 값을 찾을 수 있다.

TopDown(재귀) vs BottomUp(반복문)
전자는 가독성이 좋고, 점화식을 이해하기 쉽지만, 함수를 호출하므로 메모리와 시간이 더 소요된다.
후자는 가독성이 안좋지만, 함수를 호출하지 않기 때문에 시간과 메모리적 측면에서 비교적 효율적이다.

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

2294번: 동전 2

세 번째 DP문제이다. 조금 감이 오기 시작하면서 점화식에 접근은 하지만, 역시나 바텀업으로 푸는 것은 너무 어렵다. 특히나 이 문제는 아직 풀지 못했다.. 

n개의 동전이 존재하고, 각 동전의 번호를 0 ~ n-1이라고 해보자. 각 동전의 가치는 cost[i][에 저장한다.
f( n , k )를 n번째 동전부터 시작하여 가치합을 k로 만들고자 할 때, 최소 동전 개수를 구하는 함수라고 하자. 

1. BaseCase찾기
문제에서 알 수 있듯이 경우의 수가 존재할 수도, 아닐 수도 있다. 위에서 정의한 함수에 의해서 두 가지 경우의 수를 정의해보자. 
n이 주어진 동전의 가장 끝에 다다라 선택할 동전이 없는 경우, 즉 n = N인 경우 만들고자 하는 가치합 k가 0이라면 만들 수 있는 경우의 수가 없기 때문에 0이다. 끝에 다다르기 전에 선택한 동전으로 가치합을 모두 구성했다는 것이다.

하지만 k>0이라면 어떨까? 이미 모든 동전을 선택하고 난 후에도 가치합이 남아 있다면 현재 동전의 가치들로는 만들 수 없는 가치합이라는 뜻이 된다.

if(n == N){
	if(k == 0 ) return 0
    else return INF
}

위의 수식을 실제로는 간단하게 삼항연산자를 사용했다. 

2. recursive case 찾기 

이제는 실제로 동전을 찾는 경우의 수에 대해서 생각해봐야 하는데, 문제에서는 동전의 가치가 같은 동전이 있을 수도 있고, 같은 동전을 여러 번 사용해도 된다고 했다.

여기서는 고려해야 할 것이 이번 동전을 사용할 것인지 안 할 것인지를 체크해봐야 하는데, 그 여부는 현재 동전의 가치와 목표 가치합으로 따져본다. 

만일, 아직 동전이 남아 있다고 했을 때, n번 동전의 가치 cost[n] 목표 가치합 k보다 크다면 어떻게 해야 할까? 당연히 사용하지 않고 다음으로 넘어가야 한다. 더도 말고 덜도 말고 정확히 k를 맞춰야 하기 때문이다. 즉 여기서 다음 동전을 선택한다고 말하는 것은 f( n+1, k )값을 구하라는 것이다. 

그렇다면 위와는 반대의 상황을 따져보면 된다. cost[n] <= k라면? 같은 동전을 한 번만 사용할 것인지 혹은 여러 번 반복해서 사용할 것인지에 대한 것을 생각해보아야 하는데. 우리는 재귀를 하고 있기 때문에 생각보다 단순하다. 
f ( n , k ) 를 구하는 상황에서 cost[n] <= k이고, 같은 동전을 가능할 때까지 반복적으로 사용하기 위해서는 아래와 같이 한다. 
f ( n , k - cost[n] ) + 1
basecase에 도달해서 동전을 선택하는 것이 성공하면 0을 리턴하기 때문에 실질적인 count는 +1이 되는 것이고, 
k - cost[n]으로 k값을 줄여가다가 cost[n] <= k를 만족하지 않게 되면 재귀를 멈추게 되는 것이다.

package DynamicProgamming;

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

public class _2294_동전2 {
	static int N, K;
	static int INF = 20000000;
	static int dp[][];
	static int cost[];
	
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		cost = new int[N+1];
		dp = new int[N+1][K+1];
		
		for(int [] i : dp) {
			Arrays.fill(i, -1);
		}
		for(int i=0; i<N; i++) {
			cost[i] = Integer.parseInt(br.readLine());
		}
		
		int min = coin(0, K);
		
		System.out.println(min==INF ? -1 : min);
	}


	private static int coin(int n, int k) {
		// TODO Auto-generated method stub
		if(n==N) return k==0 ? 0 : INF;
		if(dp[n][k] != -1) return dp[n][k];
		
		int res = coin(n+1, k);
		if(k >= cost[n]) res =  Math.min(res, coin(n, k-cost[n])+1);
		
		dp[n][k] = res;
		
		return res;
	}
}