DP > 카드 구매하기 (11052번)

문제

---

풀이

쉽지않다...

d[n] = n개의 카드를 구매하기 위한 최대 지불 금액

여기서도 d[n]을 구하는 과정이 제일 중요하다

우선 p[n]은 n개의 카드가 들어있는 카드팩의 가격이다.

여기서도 주목하는 점은 마지막 선택하는 카드팩이 된다!

d[n]에서 만약 마지막 고른 카드팩이 P1이라면? 남은 것은 d[n-1]일 것이다

또 P2면 d[n-2]가 된다 이렇게 쭉 고민하면 결론은 뭐다?

d[i] = MAX(P[j] + d[i-j]) 가 된다!

전체 경우의 수에서 최댓값을 고르면 되는거다!

아직까진 dp가 쉽지 않은 것 같다.. 하다보면 늘겠지.. 꾸준히 해보자..!

 

---

코드

#include <iostream>
#include <stdio.h>
#define MAX 1001

int d[MAX];
int p[MAX];

using namespace std;

int main()
{
    ///bottom-up
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;
    int res=0;
    cin>>n;
    
    for(int i=1;i<=n;i++)
    {
        cin>>p[i];
    }
    
    d[0]=0;
    d[1]=p[1];
    
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            res=p[j]+d[i-j];
            if(res>d[i]) d[i]=res;
        }
    }
    printf("%d\n",d[n]);
    return 0;
}

중첩 반복문 부분을 조금 고민했다

아니 이거 하는데 자꾸 연락오고 난리도 아니어서...

암튼 저기는 계속 반복문 돌면서 최솟값 구해야되니까 이중반복분했고

저기 위에 보면 p[i] 배열을 인덱스가 1부터 받는다.

그래야지 이중반복문에서 불러오기 편함

p[1]이 1장 들어있는 카드팩이고 가격이 저장되는거라 안그러면 뒤에서 i-1로 계산해야되는데, 그러기 머리아파서 그냥 저렇게 받았어

저게 더 쉬운것같음