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

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

11052번: 카드 구매하기

 

 

방법 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();
            }
 
            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] > 0) {
            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>
 
using namespace std;
 
const int MAX = 1000;
int cost[MAX + 1];
int max_cost[MAX + 1];
 
// 점화식 : D[n] = max(D[n - i] + P[i])
int get_max_cost(int n)
{
    if (max_cost[n] > 0)
    {
        return max_cost[n];
    }
 
    if (n <= 0)
    {
        return 0;
    }
 
    int max = 0;
    for (int i = 1; i <= n; i++)
    {
        int temp = get_max_cost(n - i) + cost[i];
        max = (max < temp) ? temp : max;
    }
 
    return max_cost[n] = max;
}
 
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];
    }
    
    get_max_cost(n);
 
    cout << max_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++) {
                for (int j = 1; j <= i; j++) {
                    int temp = result[i - j] + arrCosts[j];
                    result[i] = (temp > result[i]) ? temp : result[i];
                }
            }
            
            System.out.println(result[iCaseCount]);
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

 

c++소스

#include <iostream>
#include <algorithm>
#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);
    for (int i = 1; i <= n; i++)
    {
        cin >> cost[i];
    }
 
    // 점화식 : D[n] = max(D[n - i] + P[i])
    vector<int> max_cost(n + 1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            max_cost[i] = max(max_cost[i], max_cost[i - j] + cost[j]);
        }
    }
 
    cout << max_cost[n];
 
    return 0;
}

 

바텀업이 탑다운보다 가독성과 효율이 더 큰 문제

 

 

TIP1

문제에서 P(N) 이 카드 N장을 구매하는 비용이라 했고,

D(N)을 카드를 P(1)부터 N장 구매했을 때 최대 비용 이라고 하자.

 

타일링 문제를 떠올리면서 식을 세워보면, 아래와 같다. 

D(N)  =  MAX( D(N - 1) + P(1) ,  D(N - 2) + P(2) , ... , D(1) + P(N) )

 

 

따라서 D(N)을 구하려면 먼저 D(1), D(2) ... D(N - 1) 을 구해야 하는데...

각각 식을 세워보면 아래와 같다. 

 

D(N - 1)  =  MAX( D(N - 2) + P(1) ,  D(N - 3) + P(2) , ... , D(1) + P(N - 1) )

D(N - 2)  =  MAX( D(N - 3) + P(1) ,  D(N - 4) + P(2) , ... , D(1) + P(N - 2) )

...

D(1) = MAX( D( 0 ) + P(1) )

 

 

즉, D(1)부터 D(K)까지 각각 for문을 돌려서 카드가 K장일 때의 최대값을 구해야 한다. 

간단한 숫자 대입과 표현

 

바텀업 방식으로 나열해보면,

D(1) = MAX( D(0) + P(1) )             <-- D(0) = 0

D(2) = MAX( D(1) + P(1) , D(0) + P(2) )

D(3) = MAX( D(2) + P(1) , D(1) + P(2) , D(0) + P(3) )

...

D(K)  =  MAX( D(K - 1) + P(1) ,  D(K - 2) + P(2) , ... , D(K - K) + P(K) )

--> i , j

이를 표현하면 아래와 같다.

            for (int i = 1; i <= iCaseCount; i++) {
                for (int j = 1; j <= i; j++) {
                    int temp = result[i - j] + arrCosts[j];
                    result[i] = (temp > result[i]) ? temp : result[i];
                }
            }

 

 

 

 

 

TIP2

점화식을 세울 때,

주어진 수열을 P(n) , 이로부터 계산한 2차 수열을 X(n) 이라 하면 

X(1)부터 확정시키면서 X(n)을 구하자.

 

for (int i = 1; i <= iCaseCount; i++) { //( X )
    for (int j = i; j <= iCaseCount; j += i) {
        int temp = Math.max(arrCosts[j], result[j - i] + arrCosts[i]) ;
        result[j] = (temp > result[j]) ? temp : result[j];
    }
}

처음에 잘못 생각하고 했던 코딩. 

뒤죽박죽 순서로 D(n)을 구하기 때문에 틀렸다. 

 

for (int i = 1; i <= iCaseCount; i++) { //( O )
    for (int j = 1; j <= i; j++) {
        int temp = result[i - j] + arrCosts[j];
        result[i] = (temp > result[i]) ? temp : result[i];
    }
}

올바른 코딩. D(1) 부터 확실히 구해나가므로,

D(2), D(3) 값을 안정적으로 구할 수 있다.