챕터3-6. DP | 문제 풀이1 - (5) 백준 No.11052 : 카드 구매하기

카드 구매하기 문제

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

문제요약

카드 N개를 구매하려고 하는데,
i개를 묶어서 파는 카드 묶음의 가격이 P[i]일 때, N개를 구매하며 지불할 수 있는 최대금액 구하기

해결방법

1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다.
- D[N] = "N개를 모두 구매하며 지불할 수 있는 최대 금액"

2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다.
- 정수 N이 주어지고, 앞에 어떤 조합이 존재하고 마지막 조합에서 아래와 같은 방법 중 1가지를 선택할 수 있다.

N = O+O+O+...+O+A

Case1) 마지막 A에서 1개가 묶어진 것을 지불하고 사는 경우
- 지불할 수 있는 최대 금액은 D[N] = D[N-1] + P[1]

Case2) 마지막 A에서 2개가 묶어진 것을 지불하고 사는 경우
- 지불할 수 있는 최대 금액은 D[N] =  D[N-2] + P[2]

Case3) 마지막 A에서 3개가 묶어진 것을 지불하고 사는 경우
- 지불할 수 있는 최대 금액은 D[N] =  D[N-3] + P[3]
...

선택가능한 선택지 중에서 가장 큰 금액을 지불하는 것을 찾는 것이므로 D[N] = max(D[N-i] + P[i]) 으로 점화식을 생각할 수 있다.

3. 다이나믹 프로그래밍 방법을 적용할 수 있는 문제인지 확인 => 1, 2번을 거쳐야 이게 잘 보임.
- 위와 같이 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹친다.
   (Overlapping SubProblem)
- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
   (Optimal Substructure)

4. 코드구현

for (int i=1; i<=n; i++)
{
    for (int j=1; j<=i; j++)             // d[i] 한칸을 계산해내기 위한 연산
        d[i] = max(d[i], d[i-j] + p[j]);
}

* Top-Down, Bottom-Up 방식 모두 최종값이 결정되는 순서는 d[1], d[2], d[3],,, 순이다. (구현방식의 차이일 뿐)

<Top-down 방식>

(1) 구현
-> '재귀호출' 방식으로 구현
- Top-bottom 방식은 전역변수를 사용해야 구현이 쉽다.

- Top-bottom 방식은 Bottom-up방식에서 2중 for문 중 바깥 for문을 제거하고 j를 i로, i를 n으로 수정했다고 생각하면됨
- 재귀적인 호출이 일어날 때는 두번째 if(d[n] > 0) return d[n]; 을 꼭 넣어줘야 한다.(다이나믹 프로그래밍의 필수적요소)

#include <iostream>

using namespace std;

int d[1001] = {0};
int p[100001] = {0};

int getMaxPrice(int n)
{
    if(n == 0)
        return 0;

    else if (d[n] > 0)           // 이게 없으면 시간 초과됨.
        return d[n];

    for(int i = 1; i <= n; i++)  // 선택가능한 것들 중 max 가격을 선택하기 위한 내부 for문
        d[n] = max(d[n], getMaxPrice(n-i) + p[i]);

    return d[n];
}

int main()
{
    int T;
    cin >> T;
    
    // 묵음별 가격을 입력받음
    for (int i = 1; i <= T; i++)
        cin >> p[i];
    
    cout << getMaxPrice(T);
}

(2)시간복잡도
= 배열에 채워 넣어야하는 값의수 x 1칸을 채우는 복잡도
- 배열에 채워 넣어야하는 값의 수 : N
- 1칸을 채우는 복잡도 : P[i]에서 i의 범위는 1 <= i <= N 이므로 총 N번의 연산이 필요하고, 이걸 시간복잡도로 나타내면 O(N)
- 따라서 전체 시간복잡도는 N * O(N) = O(N^2)

<Bottom-up 방식>

(1) 구현
-> 'for문을 이용한 반복문'으로 구현
- Bottom-up방식은 함수를 굳이 구현하지 않아도 됨.
- 배열 대신 메모리를 효과적으로 관리하기위해 벡터를 사용할 수도 있음

#include <iostream>
#include <vector>   // vector를 사용하기 위함

using namespace std;

int main()
{
    int T;
    cin >> T;

    // 묵음별 가격을 입력받음
    vector<int> p_vec(T+1);       // 묶음별 가격, p_vec[0]은 사용안하므로 T+1 만큼 크기를 줘서 선언함.
    for (int i = 1; i <= T; i++)
        cin >> p_vec[i];
    
    // d를 전역변수가 아니라 아래와 같이 벡터로 선언하게 되면 재귀적인 함수를 호출하는 Top-down 방식을 쓰기 어려우므로 Bottom-up 방식을 사용하자.
    vector<int> d_vec(T+1);
    for(int i = 1; i <= T; i++){      // d_vec[1]부터 시작해서 d_vec[T]까지 차례로 구해나가기 위한 바깥 for문
        for(int j = 1; j <= i; j++){  // 선택가능한 것들 중 max 가격을 선택하기 위한 내부 for문
            d_vec[i] = max(d_vec[i], d_vec[i-j] + p_vec[j]);
        }
    }

    cout << d_vec[T];
}

#include <iostream>

using namespace std;

int d[1001] = {0};
int p[100001] = {0};

int getMaxPrice(int n)
{
    for (int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++)  // 선택가능한 것들 중 max 가격을 선택하기 위한 내부 for문
            d[i] = max(d[i], d[i-j] + p[j]);
    }
    
    return d[n];
}

int main()
{
    int T;
    cin >> T;
    
    // 묵음별 가격을 입력받음
    for (int i = 1; i <= T; i++)
        cin >> p[i];
    
    cout << getMaxPrice(T);
}

(2) 시간복잡도
= for 문의 반복 횟수
- 바깥 for문의 최대 반복횟수는 N이고, 내부 for문의 최대 반복횟수는 N이므로
- O(N) * O(N) = O(N^2)