(5) [C++, Java] 백준 No.11052 : 카드 구매하기

문제

풀이

- 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-6-다이나믹-프로그래밍-문제-풀이5-백준-No11052-붕어빵-판매하기-문제

# C++(Top-down 방식)
- Top-down방식은 전역변수를 사용해야 구현이 쉽다.
- 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);
}

# C++(Bottom-up 방식)
- 배열 대신 메모리를 효과적으로 관리하기위해 벡터를 사용할 수도 있음

#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);
}

#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];
}

# Java

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n+1];
        for (int i=1; i<=n; i++) {
            a[i] = sc.nextInt();
        }
        int[] d = new int[n+1];
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=i; j++) {
                if (d[i] < d[i-j] + a[j]) {
                    d[i] = d[i-j] + a[j];
                }
            }
        }
        System.out.println(d[n]);
    }
}