[11052번] 카드 구매하기

 

문제출처 :  https://www.acmicpc.net/problem/11052

 

 

문제분석

구매하려고 하는 카드의 개수 N개를 입력 받는다.

 

=> 결국 구매하려는 카드의 개수에 따라 카드 팩의 종류 수도 자동 결정이 된다.

 

그리고 두번째 줄 부터 각 카드 팩의 종류의 금액을 입력받는다.

 

Pi 에서 결국에는 i 가 그 카드팩의 개수이다.

 

 

설계

 

결국 최대값을 갱신해 가면서 N까지 도달해야 하므로 dp로 풀어야 한다는 것은 쉽게 알 수 있다.

 

그리고 만약 N번째 팩 하나만 사는 것이 최대값일 수도 있다.

for (int i = 1; i <= N; i++) {
    pay[i] = sc.nextInt();
    dp[i] = pay[i];
}

 

초기에 pay값을 입력받을 때 dp에 pay값을 같이 넣어주면 max 값을 비교할 때 훨씬 수월하다.

 

많은 dp 문제들이 이렇게 dp의 초기값을 0이 아닌 입력받은 값을 초기값으로 세팅해주면 값 비교에서 dp를 바로 쓸 수 있어 좋다.

 

for (int i = 2; i <= N; i++) {
    for (int j = 1; j < i; j++) {
        dp[i] = Math.max(dp[i], dp[j] + pay[i-j]);
    }
}

 

dp의 초기값을 pay값으로 설계하면 다음과 같이 식을 설계할 수 있다.

 

dp[j] + pay[i-j]

 

이 부분이 핵심인데 다음과 같은 사고로 식을 설계해 보았다.

 

결국 dp[j] 라는 것은 j 개의 카드를 구매했을 때 최대 값이다.

 

그럼 pay[i-j] 라는 것은 i-j 개 만큼의 카드가 들어있는 카드 팩의 금액이다.

 

결국 j + (i - j) = i 이므로 두 개를 더할 경우 총 i 개의 카드를 구매하려 했을 때의 가격임을 알 수 있다.

 

그리고 우리는 기존에 구해놨던 dp[i]와 계속 비교를 해 나가면서 최대값을 찾는 것이다.

 

이렇게 비교하면 빠짐없이 i 개의 카드를 구매하려는 모든 경우의 수 중 가격의 최대값을 얻을 수 있다.

 

 

import java.util.Scanner;

public class _11052 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int []pay = new int[N+1];
        int []dp = new int[N+1];

        for (int i = 1; i <= N; i++) {
            pay[i] = sc.nextInt();
            dp[i] = pay[i];
        }

        for (int i = 2; i <= N; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], dp[j] + pay[i-j]);
            }
        }

        System.out.println(dp[N]);
    }
}

 

 

결론

이 문제는 전형적인 쉬운 dp 문제중 하나이다.

 

그나마 어려웠던 곳이라면 Math.max()에서 dp[i]와 어떤 식을 비교해가며 전개할 것인가를 설계하는 것 이였다.

 

하지만 결국 내가 빠짐없이 비교해야 하는 것이 무엇인가에 집중하면 쉽게 구할 수 있는거 같다.

 

dp 문제는 결국 내가 구해야 하는 값이 무엇인지, 어떠한 값들을 저장해가며 식을 전개할지, 내가 저장할 값을 무엇으로 지정할건지(간혹 어려운 문제는 2개이상인 경우도 있기 때문에)

 

만 잘 정한다면 못푸는 문제는 없는거 같다.

 

그리고 이게 dp문제의 매력같다.