[BOJ] 11052. 카드 구매하기(DP)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

DP[i][j] 는 구매하려고 하는 카드의 개수가 i 개일 떄,

  j 번째 카드 팩까지 주어졌을 경우 카드 i 개를 갖기 위해 지불해야 하는 금액의 최댓값을 의미한다.

입력이 아래와 같다면

5

10 9 8 7 6

아래 그림처럼 표현할 수 있다.

먼저,

구매하려고 하는 카드의 개수가 1개일 때,

1개가 들어있는 카드팩을 구매하는 방법이 돈을 가장 많이 지불하는 방법이다.

다음으로,

구매하려고 하는 카드의 개수가 2개일 때,

j = 1,    P1 두 개 구매,    20원

j = 2,    P1 두 개 구매,    20원    

P2 한 개 구매,    9원

다음으로,

구매하려고 하는 카드의 개수가 3개일 때,

j = 1,    P1 세 개,    30원

j = 2,    P1 세 개,    30원

P1 한 개, P2 한 개,    19원

j = 3,    P1 세 개,    30원

P1 한 개, P2 한 개,    19원

P3 한 개,    8원

보면 점화식은

DP[i][j] = max(DP[i][j-1], DP[i-j][j] + P[j])

로 세울 수 있다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include <cstdio> #include <algorithm> using namespace std;   int DP[1001][1001], P[1001];   int main(void) {     int n, i, j;     //freopen("input.txt", "rt", stdin);     scanf("%d", &n);     for (i = 1; i <= n; i++)          scanf("%d", &P[i]);          for (i = 1; i <= n; i++) {         DP[1][i] = P[1];         DP[i][1] = DP[i-1][1] + P[1];     }       for (i = 2; i <= n; i++) {         for (j = 1; j <= i; j++) {             DP[i][j] = max(DP[i][j-1], DP[i - j][j] + P[j]);         }         for (; j <= n; j++) {             DP[i][j] = DP[i][j - 1];         }     }       printf("%d\n", DP[n][n]);       return 0; } Colored by Color Scripter

cs

#. Other Code

/*
reference : iny27
*/
 
#include <cstdio>
using namespace std;
int max(int p, int q) { return p > q ? p : q; }
 
int DP[1001];
 
int main(void)
{
    int n, i, j;
    // freopen("input.txt", "rt", stdin);
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        scanf("%d", &DP[i]);
 
    for (i = 1; i <= n; i++) 
         for (j = 1; j <= i/2; j++) 
            DP[i] = max(DP[i], DP[i-j] + DP[j]);
 
    printf("%d\n", DP[n]);
 
    return 0;
}

일차원 배열 하나로 문제를 해결한 코드이다.

DP[N]에서 N은 구매하려고 하는 카드의 개수가 N개일 때,

지불해야 하는 금액의 최댓값을 의미

구매하려고 하는 카드의 개수가 1개일 때,

P1을 구매할 경우

DP[1] = max(DP[1], DP[0] + 10) = max(10, 10) = 10 

구매하려고 하는 카드의 개수가 2개일 때,

P2를 구매할 경우와, P1x2를 구매할 경우

DP[2] = max(DP[2], DP[1] + 10) = max(9, 20) = 20

구매하려고 하는 카드의 개수가 3개일 때,

P3를 구매할 경우, P1x3을 구매할 경우

DP[3] = max(DP[3], DP[2] + 10) = max(8, 30) = 30

구매하려고 하는 카드의 개수가 4개일 때,

P4를 구매할 경우, P1x4을 구매할 경우

DP[4] = max(DP[4], DP[3] + 10) = max(7, 40) = 40

그리고

P1x4을 구매할 경우우, P1x4을 구매할 경우

DP[4] = max(DP[4], DP[2] + 20) = max(40, 40) = 40

* 일차원 배열로 해결하려고 하니 복잡하긴 하다..

  그래도 최적화는 중요한 부분이므로 익숙해질 수 있도록 해야지..