[백준] 16194

문제 개요

이 문제는 특정 개수 (N)의 PS(Problem Solving) 카드를 최소 비용으로 구매해야 하는 문제입니다. 카드는 여러 개의 카드가 포함된 카드팩 형태로만 구매할 수 있으며, 각 카드팩은 포함된 카드의 수와 가격이 다릅니다. 주어진 카드팩 가격을 이용해 정확히 (N)개의 카드를 구매하는 데 필요한 최소 비용을 구하는 것이 목표입니다.

접근 방법

이 문제는 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있습니다. 접근 방법을 단계별로 설명하겠습니다.

1. 동적 계획법 배열 정의:
   cost 배열을 정의합니다. 이 배열에서 cost[i]는 정확히 i개의 카드를 구매하는 데 필요한 최소 비용을 나타냅니다.

2. 비용 배열 초기화:

   • cost[0]은 0으로 초기화합니다. 이는 0개의 카드를 구매하는 데 비용이 0이기 때문입니다.
   • 1부터 N까지의 각 i에 대해 cost[i]는 arr[i]로 초기화합니다. 이는 i개의 카드를 포함한 카드팩을 구매하는 경우의 비용입니다.

3. 동적 계획법 전이:
   1부터 N까지의 각 카드 수 i에 대해, j와 i-j로 나누어 i개의 카드를 구성할 수 있는 모든 방법을 확인합니다. 이는 다음과 같은 논리를 사용합니다:

   for (int j = 1; j < i/2 + 1; j++) {
       cost[i] = cost[i-j] + cost[j] > cost[i] ? cost[i] : cost[i-j] + cost[j];
   }

   이를 통해 i개의 카드를 구성하는 모든 가능한 카드팩 조합 중 최소 비용을 선택합니다.

4. 결과 출력:
   마지막으로 N개의 카드를 구매하는 데 필요한 최소 비용이 cost[N]에 저장되며, 이 값을 출력합니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class P16194 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");

        int[] arr = new int[N+1];
        for(int i = 1; i < N+1; i++){
            arr[i] = Integer.parseInt(input[i-1]);
        }

        int[] cost = new int[N+1];
        cost[0] = 0;

        for(int i = 1; i < N+1; i++){
            cost[i] = arr[i];
            for (int j = 1; j < i/2 + 1; j++){
                cost[i] = cost[i-j] + cost[j] > cost[i] ? cost[i] : cost[i-j] + cost[j];
            }
        }
        System.out.println(cost[N]);
    }
}

사고 과정 설명

1. 문제 이해
   이 문제의 핵심은 다양한 카드팩 옵션을 고려하여 정확히 N개의 카드를 최소 비용으로 구매하는 것입니다.

2. 동적 계획법 접근
   동적 계획법은 이전에 계산된 결과를 바탕으로 결정을 내려야 하는 문제에 적합합니다. 이 문제는 1부터 N까지의 모든 카드 개수에 대한 최소 비용을 계산하는 것으로, 작은 부분 문제를 해결하여 전체 문제를 해결하는 방법입니다.

3. 초기화 및 전이
   초기화 단계에서는 기본적인 경우를 처리하고, 전이 단계에서는 작은 부분 문제들의 해결 결과를 이용하여 현재 문제를 해결합니다. 이렇게 함으로써 모든 가능한 카드팩 조합을 고려하여 최적의 해를 찾습니다.

4. 최적화 통찰
   중첩된 루프 구조는 모든 가능한 카드팩 조합을 고려하고, 항상 최소 비용을 선택하도록 합니다. j < i/2 + 1 조건을 사용하여 내부 루프를 최적화하여 관련 있는 부분 문제만 고려합니다.

결론

이 접근 방법은 동적 계획법의 강력함을 이용하여 효율적으로 정확히 N개의 카드를 최소 비용으로 구매하는 방법을 계산합니다. 작은 부분 문제들의 해결 결과를 결합하여 최적의 해결책을 구조적으로 찾을 수 있습니다.