[백준 - 16194번] 카드 구매하기 2 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 10일차

 

16194번: 카드 구매하기 2

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

www.acmicpc.net

어떤식으로 접근했는지?

이문제는 카드 구매하기 1에 이어 같은문제인데, 이번에는 최소값을 구하는 게 문제이다.

문제는 최소값을 찾으려면 각 N에 대해서 경우를 다 따져서 확인을 해봐야하는데, 이 최대값의 경우 경우의 수가 1개의 경우만 생기는데, 최소값의 경우 각 경우마다 최소값이 될 경우가 늘어난다고 생각했습니다. 

그래서 N의 최소값을 구하기위해서 N-1~ 0 의 최소값을 최대로 더해주고, 부족한 카드를 실제로 남은 걸 더하는 방식으로 모든 카드를 채워 최소값을 만듭니다. 

 

/** 2020. 2. 28. 오후 10:23:59
 * @author ventulus95
 */
package codeBaekJoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class No16194_CardBuy2 {
	static int cnt[];
	static int arr[];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String tc = br.readLine();
		arr = new int[N+1];
		cnt = new int[N+1];
		StringTokenizer st = new StringTokenizer(tc, " ");
		for(int i =1; i<=N; i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.fill(cnt, Integer.MAX_VALUE);
		cnt[0] = 0;
		cnt[1] = arr[1];
		for(int i=2; i<= N; i++){
			for(int j=1; j<=i; j++){
				int temp = i-j;
				if(temp!=0){
					int div = i/temp;
					int mod = i%temp;
					cnt[i] = Math.min(cnt[i], cnt[temp]*div+arr[mod]);
				}
				else{
					cnt[i] = Math.min(cnt[i], arr[i]);
				}
			}
		}
		System.out.println(cnt[N]);
	}
}

근데 더 효율적인 방법이 있었다.

물론 이 방식도 맞긴합니다. 맞는데 저 방식을 명확하게 바꿔서 보일수도 있는데 

결국 temp는 cnt[i]의값을 구하기 위해서 cnt[i-j]에서 이미 구한 최소값 + arr[j]값을 더한다고 해서 그 전체 합이 달라지지 않습니다. 

즉, cnt[temp]*div + arr[mod] 를 통해서 나온 최소값을 만들기위한 경우 = cnt[i-j]+ arr[j]을 해서 만들어지는 경우

결국 같은 방식이긴하지만, 점화식은 뒤의 것이 좀 더 직관적이죠. 저는 1~n-1까지의 경우중에서 그걸 최대한 많이 쓰고 남은 카드갯수를 더하는 방식인 것에 차이인것입니다. 

 

직관적인 점화식은 cnt[i-j]+ arr[j]를 활용하시면됩니다.