[Java]백준 16194번 :: 카드 구매하기 2

백준 온라인 저지 16194번 - 카드 구매하기2

Java 알고리즘 문제풀이

풀이

DP(다이나믹 프로그래밍) 문제입니다.

큰 문제를 작은 단위의 문제로 생각해서 푸는 알고리즘인데, 코딩테스트에 자주 출제되는 문항이다.

 

문제를 해석해보면

• 카드 N개를 구매해야한다.
• 카드팩에 들어있는 카드가 적은 것부터 산다.
• 카드 N개를 구매하는데 드는 비용의 최소를 구하는 문제이다.

 

DP를 풀때 일반항 형태로 정의하는 것이 중요하다.

 

일단, 케이스 단위로 생각해보자.

카드 i개를 구매하는 방법은?

• 카드 1개가 들어있는 카드팩을 구매하고, 카드 i-1개를 구입한다.
• 카드 2개가 들어있는 카드팩을 구매하고, 카드 i-2개를 구입한다.
• 카드 3개가 들어있는 카드팩을 구매하고, 카드 i-3개를 구입한다.

...

 

일반화 시키면 D[i] = P[n] + D[i-n] 이다. 

n은 1, 2, 3 ... n이고, P[n]은 가격이다.

for (int i = 1; i <=n; i++) {
	for (int j = 1; j <=i; j++) {
		D[i] = Math.min(D[i], arr[j] + D[i-j]);
	}
}

이렇게 표현할 수 있다.

 

import java.util.Scanner;

public class Beak16194 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] arr = new int[n + 1];
        int[] d = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            arr[i] = sc.nextInt();
            d[i] = Integer.MAX_VALUE;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                d[i] = Math.min(d[i], d[i - j] + arr[j]);
            }
        }

        System.out.println(d[n]);

        sc.close();
    }
}