[백준] 11052번 : 카드 구매하기

문제

 

---

풀이

 

문제를 풀고 다른 이들의 코드를 찾아봤는데, 다들 범위처리를 나와 다르게 했다.

근데 내가 더 효율적인 것 같고...이렇게 해도 될 것 같기도 하고 그리고 일단 AC를 받았기 때문에 내 풀이로 설명한다.

 

카드 i개를 사는 방법은 다음과 같다.

 

(카드 1개가 들어있는 팩 구매) + (카드 i-1개 구매)

(카드 2개가 들어있는 팩 구매) + (카드 i-2개 구매)

...

(카드 i-1개가 들어있는 팩 구매) + (카드 1개 구매)

(카드 i개가 들어있는 팩 구매)

 

팩 구매가 P, 카드 구매가 dp라고 놓으면 점화식은 금방 나온다.

 

근데, 다른 풀이들을 보니 여기까지는 똑같은데 dp[0] 부터 dp[i-1] 까지를 전부 비교하는 코드로 작성하고 있었다.

 

예시를 쉽게하기 위해 카드가 4개 있다고 하자.

카드를 n개 사는 방법은 n을 1~n까지의 숫자의 합으로 나타내는 것과 같다.

 

카드를 1개 사는 방법 : 1

카드를 2개 사는 방법 : 1+1, 2

카드를 3개 사는 방법 : 1+1+1, 2+1, 3

카드를 4개 사는 방법 : 1+1+1+1, 2+1+1, 3+1, 2+2, 4

 

위의 점화식에 따르면 카드를 4개 살때의 최댓값은

P[1]+dp[3], P[2]+dp[2], P[3]+dp[1], P[4] 중에서 최댓값을 찾는 것과 같다.

 

P[4}는 열외로 두고 P[1]+dp[3]과 P[2]+dp[2]를 하나로 묶고 P[3]+dp[1]을 따로 묶도록 하겠다.

 

P[1]+dp[3]이 커버할 수 있는 범위는 카드를 3개 사는 방법인 1+1+1, 2+1, 3에 각각 1을 더한 것이다.

그니까 1+1+1+1, 2+1+1, 3+1이 되겠다.

 

P[2]+dp[2]가 커버할 수 있는 범위는 카드를 2개 사는 방법인 1+1, 2에 각각 2를 더한 것이다.

그니까 1+1+2, 2+2가 되겠다.

 

같은 원리로 P[3]+dp[1]은 1+3을 커버할 수 있다.

 

이렇게 보면 알 수 있겠지만 후자가 커버하는 경우의 수는 이미 전자에서 등장한 경우의 수다.

그렇기 때문에 굳이 i번 비교할 필요없이 i/2번만 비교하면 된다.

---

소스코드

 

#include <iostream>
#include <algorithm>

using namespace std;

int dp[1001];
int cost[1001];

int dpMax(int n) {
    dp[1] = cost[1];
    for (int i = 2; i <= n; i++) {
        int result = cost[i];
        for (int j = 1; j <= (i / 2); j++) //범위를 여기까지만 해도 될 것 같은데?
            result = max(result, cost[j] + dp[i - j]); //j개의 카드가 들어있는 팩 1개, 나머지 카드 i-j개를 사는 최댓값
        dp[i] = result;
    }
    return dp[n];
}

int main() {
    int N;

    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> cost[i];
    cout << dpMax(N);
}

전체 소스코드다.

 

    for (int i = 2; i <= n; i++) {
        int result = cost[i];
        for (int j = 1; j <= (i / 2); j++) //범위를 여기까지만 해도 될 것 같은데?
            result = max(result, cost[j] + dp[i - j]); //j개의 카드가 들어있는 팩 1개, 나머지 카드 i-j개를 사는 최댓값
        dp[i] = result;
    }

result 변수에 우선 카드를 단품 팩 하나로 사는 경우인 cost[i]를 담는다.

그리고 i/2 만큼만 반복문을 돌면서 result 값을 갱신한다.