[알고리즘][DP][11052] 붕어빵 판매하기

[알고리즘][DP][11052] 붕어빵 판매하기

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

[풀이]

• 마찬가지로 <점화식 구하기>가 가장 중요하다.
• Q[n-1] 과 Q[n]의 관계를 잘 보자!!!!!!!!!!!!!
• D[n]  = n개를 팔아서 얻을 수 있는 최대 수익
• P[i] = i개로 이루어진 세트의 가격 이라 할 때,
• o + o + o + o + ... + o + i = n (세트의 갯수를 모두 더하면 n)
• 마지막에 더한 i 세트의 가격 P[i]
• P[i]가 1 일 경우, D[n-1] 이 된다.
• P[i]가 2 일 경우, D[n-2] 가 된다.
• ...
• P[i]가 i 일 경우, D[n-i] 가 된다.
• 이 때, D[n] = MAX(P[i] + D[n-i]) 라는 점화식을 도출할 수 있다. (이미 D[n-i]는 최대값이므로 MAX(P[i])로 봐도 무방)

[코드]

package algorithm_basic;
 
import java.util.Scanner;
 
public class q_11052 {
    static int[] D;
    static int[] price;
    public static void main(String[] args)   {
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt(); //붕어빵의 수
        
        price = new int[num+1];
        for(int i=1;i<num+1;i++) {
            price[i] = scan.nextInt();    
        }
        D = new int[num+1];
        System.out.println(calc(num));
    }
 
    public static int calc(int num) {
        
 
        for(int i=1;i<=num;i++) {
            for(int j=1;j<=i;j++) {
                if(D[i]<D[i-j]+price[j]) {
                    D[i] = D[i-j]+price[j];
                }
            }
        }
        return D[num];
    }
 
}