카드구매하기 _ 백준 11052& 백준 16194

 

이번에도 역시 DP와 관련된 문제이다.

11052

카드 N개를 구매하는 비용의 최대값을 구하는 문제.

카드 N개를 구매하는 비용의 최대값을 d[N]이라고 하면 d[N] = max(d[i] + d[N-i]) 이다.

 

그러므로 d[1]의 값을 넣고, 그 다음 값부터는 for문을 통해서 확인하며 수행한다.

여기서 j의 값이 i/2인 이유는 i/2이후부터는 d[j] + d[i-j]의 순서만 다를 뿐, 결과는 같기 때문에  계산을 줄이고자 값을 제한한 것이다.

//11502 - 카드 구매하기

#include <cstdio>
using namespace std;
int d[1001];
int f[1000];
int main(void)
{
    int count;
    int num;
    int i = 1;

    scanf("%d", &count);
    num = count;

    while (count--)
    {
        scanf("%d", &f[i++]);
    }

    d[1] = f[1];
    for (int i = 2; i <= num; i++)
    {
        int max = f[i];
        for (int j = 1; j <= i / 2; j++)
        {
            if (d[j] + d[i - j] > max)
                max = d[j] + d[i - j];
        }
        d[i] = max;
    }
    printf("%d", d[num]);
    return 0;
}

16194

카드 N개를 구매하는 비용의 최소값을 구하는 문제

위의 문제와 동일하지만, 최소값이라는 점에서 다르다. 

그러므로 위에서 max로 된 것을 min으로 바꾸고, 부등호를 바꾸면 된다.

//16194 카드 구매하기 2

#include <cstdio>
using namespace std;
int d[1001];
int f[1000];
int main(void)
{
    int count;
    int num;
    int i = 1;

    scanf("%d", &count);
    num = count;

    while (count--)
    {
        scanf("%d", &f[i++]);
    }

    d[1] = f[1];
    for (int i = 2; i <= num; i++)
    {
        int min = f[i];
        for (int j = 1; j <= i / 2; j++)
        {
            if (d[j] + d[i - j] < min)
                min = d[j] + d[i - j];
        }
        d[i] = min;
    }
    printf("%d", d[num]);
    return 0;
}