[C++] 백준 11052번 - 카드 구매하기

---

0. 문제

 

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

 

1. 아이디어

 

1) 해당 문제에서 dp는 N개를 사기 위한 최대 금액값!

 

2) 처음 생각했을 땐 dp[N]은 dp[N-1] + P1이라고 생각했지만 테스트케이스에서 볼 수 있듯이 그러지 않은 경우가 있었다. 예를 들어 카드 4개를 사려고 구매하려고 할 때 2개 포함된 카드팩 2개를 사는게 더 금액의 값이 큰 경우가 있다!

 

3) 그래서 해당 경우까지 모두 고려해주기 위해서 반복문을 사용했다. (물론 시간을 고려했다)

(이때, 순열이 아니라 조합으로 봐야한다!)

 

2. 소스코드

 

#include <iostream>
int main()
{
    int N, price[1001], dp[1001];
    std::cin >> N;
    
    for (int i = 1; i <= N; i++)
        std::cin >> price[i];
    dp[1] = price[1];
 
    for (int i = 2; i <= N; i++)
    {
        int max = price[i];
        for (int j = i - 1; j >= i / 2; j--)
        {
            int temp = dp[j] + dp[i - j];
            if (temp > max) max = temp;
        }
        dp[i] = max;
    }
    std::cout << dp[N];
}

 

3. 결과

 

 

4. 피드백

 

• ㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎ

---