[BOJ]16194번: 카드 구매하기 2(java, c++)

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

16194번: 카드 구매하기 2

 

방법 1: Top-down

import java.util.Scanner;
 
public class Main {
 
    public static int[] arrCosts;
    public static int[] result;
    public static void main(String[] args) {
 
        try {
            Scanner sc = new Scanner(System.in);
 
            int iCaseCount = sc.nextInt();
            arrCosts = new int[iCaseCount + 1];
            result = new int[iCaseCount + 1];
            
            for (int i = 1; i <= iCaseCount; i++) {
                arrCosts[i] = sc.nextInt();
                result[i] = 1000*10000;
            }
 
            calculate(iCaseCount);
            
            System.out.println(result[iCaseCount]);
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    public static int calculate(int num) {
        if (num == 0) {
            return 0;
        }
        
        if (result[num] < 1000*10000) {
            return result[num];
        }
        
        for (int i = 1; i <= num; i++) {
            int temp = calculate(num - i) + arrCosts[i];
            if (result[num] > temp) {
                result[num] = temp;
            }
        }
        return result[num];
    }
}

 

c++소스

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int MAX = 1000;
int cost[MAX + 1];
int min_cost[MAX + 1];
 
// 점화식 : D[n] = min(D[n - i] + P[i])
int get_min_cost(int n)
{
    if (n <= 0)
    {
        return 0;
    }
    if (min_cost[n] > 0)
    {
        return min_cost[n];
    }
 
    for (int i = 1; i <= n; i++)
    {
        int temp = get_min_cost(n - i) + cost[i];
        // 문제에서 카드값은 1 ≤ Pi ≤ 10,000 이므로, 
        // (min_cost == 0) 여부를 기준으로 구분해도 상관없다
        min_cost[n] = (min_cost[n] < 0) ? temp : min(min_cost[n], temp);
    }
 
    return min_cost[n];
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> cost[i];
        // 값을 아직 구하지 않았다는 뜻
        min_cost[i] = -1;
    }
    
    get_min_cost(n);
 
    cout << min_cost[n];
 
    return 0;
}

 

방법 2: Bottom-up

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
 
        try {
            Scanner sc = new Scanner(System.in);
 
            int iCaseCount = sc.nextInt();
            int[] arrCosts = new int[iCaseCount + 1];
            int[] result = new int[iCaseCount + 1];
            
            for (int i = 1; i <= iCaseCount; i++) {
                arrCosts[i] = sc.nextInt();
            }
 
            for (int i = 1; i <= iCaseCount; i++) {
                
                result[i] = 1000*10000;
                for (int j = 1; j <= i; j++) {
                    
                    int temp = result[i - j] + arrCosts[j];
                    if (temp < result[i]) {
                        result[i] = temp;
                    }
                }
            }
            
            System.out.println(result[iCaseCount]);
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

 

c++소스

#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin >> n;
    vector<int> cost(n + 1);
    vector<int> min_cost(n + 1);
    
    for (int i = 1; i <= n; i++)
    {
        cin >> cost[i];
        // 값을 아직 구하지 않았다는 뜻
        min_cost[i] = -1;
    }
 
    // 점화식 : D[n] = min(D[n - i] + P[i])
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            // 문제에서 카드값은 1 ≤ Pi ≤ 10,000 이므로, 
            // (min_cost == 0) 여부를 기준으로 구분해도 상관없다
            if (min_cost[i] < 0 || min_cost[i] > min_cost[i - j] + cost[j])
            {
                min_cost[i] = min_cost[i - j] + cost[j];
            }
        }
    }
 
    cout << min_cost[n];
 
    return 0;
}

 

카드 구매하기1과 마찬가지로, 바텀업이 가독성&효율성이 더 뛰어나다. 

 

 

TIP

카드구매하기1 문제와 같은 형식이다.

단, 최솟값을 구하므로 초기값을 문제에서 주어진 최대값 (1000*10000) 으로 대입해두어야

값의 비교가 용이하다.