[BOJ] #11052 카드 구매하기

시간 제한	메모리 제한	정답 비율
1초	256 MB	59.766%

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

11052번: 카드 구매하기

 

문제

구매하고 싶은 카드의 개수 N 과, 1 ~ N 개의 카드 묶음의 가격 P[1] ~ P[n]이 두 줄에 나타나게 된다. 따라서 P[1]은 카드 한 개를 구매했을 때의 가격, P[2]는 카드 두 개를 구매했을 때의 가격, P[3]은 카드 세 개를 구매했을 때의 가격이 된다.

이 때 카드 N 개를 갖기 위해 지불해야하는 금액의 최댓값을 출력해야한다.

 

해결방안

입력으로 주어진 P[i] 를 기준으로

• i 개의 카드를 구매한다고 가정한다.
• j 는 i 보다 작은 수 | 0 < j < i
• j 로 i 를 만들수 있는 조합을 생각한다.
• 주어진 P[i] 와 조합들의 가격을 비교하여 최대값을 dp[i] 에 저장한다.

조합은 j로 i 를만드는 경우의 수를 뜻한다.
조합들의 가격은 조합들 중 가격의 합이 최대인 것이다.

1 부터 i 까지 차례대로 위와 같은 방법으로 dp[i] 를 채운다면,

dp[i]는 i 개의 카드를 갖기 위해 지불해야하는 금액의 최대값이 된다.

마찬가지로 j 와 dp[j]에 해당하는 조합과 조합들의 가격도 간단하게 처리할 수 있게 된다.

두 개의 j 의 조합으로 나타낼 수 있는 최대값 = dp[j] + dp[i-j]

이렇게 카드 개수에 대한 금액의 최대값을 저장함으로써 고려하는 범위가 좁아지게 되어 문제를 쉽게 풀 수 있게 된다. 

 

메모리	시간
1992 KB	0 ms

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int n, arr[1005], dp[1005];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }
    dp[1] = arr[1];
    for (int i = 2; i <= n; i++) {
        int Max = arr[i];
        for (int j = 1; j < i; j++) {
            Max = max(Max, dp[j] + dp[i - j]);            
        }
        dp[i] = Max;
    }
    printf("%d", dp[n]);
    return 0;
}