[DP] 백준 #11052 / 붕어빵 판매

오늘은 DP문제. 삼성의 '퇴사'문제와 SW Expert Academy의 '수영장' 문제와 비슷한 느낌을 받았다.

그래서 처음에는 DFS로 Backtracking 기법을 이용했는데, 시간 초과가 떴다... 코드는 다음과 같다.

/*    boj.kr/11052 붕어빵 판매하기 문제
 * 
 * 1.     붕어빵 장수 해빈이에게는 현재 붕어빵이 N개 남아있다.
 * 2.     붕어빵 세트 메뉴를 구성해서 수익을 최대로 만들어보려고 한다.
 * 3.     세트 메뉴의 가격은 이미 정해져 있다.
 * 4.     붕어빵 i개로 이루어진 세트 메뉴의 가격은 Pi원이다.
 * 5.     붕어빵이 4개 남아 있다고 가정했을 때, 1개 팔때는 1원 / 2개는 5원 / 3개는 6원 / 4개는 7원인 경우
 *         해빈이가 얻을 수 있는 최대 수익은 10원이다. 2개 2개로 붕어빵 나눠서 팔면 되니까.
 * 6.     세트메뉴 가격이 주어졌을 때, 해빈이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하라.
 * 
 * [Input]
 * 
 * 1. N(해빈이가 갖고 있는 붕어빵의 수. 1 ~ 1000)
 * 2. Pi가 P1부터 Pn까지 순서대로 주어진다. (1 <= pi <= 10000)
 * 
 * [Output]
 * 해빈이가 얻는 최대 수익을 출력
 * 
 * DP문제. dfs로 풀 수 있을것 같음.
 */
 
import java.util.Scanner;
 
public class boj_11052_boong_a_bbang {
    
    private static int N;
    private static int SET_MENU[];
    private static int MAX_PRICE;
    
    public static void dfs(int bbang,int price) {
        if(bbang == 0) {
            if(price > MAX_PRICE) MAX_PRICE = price;
            return;
        }
        for(int i=N;i > 0;i--) 
            if(bbang-i >= 0) dfs(bbang-i,price+SET_MENU[i]);
        // 판매할 때마다 빵의 갯수는 줄지만 가격은 늘어난다.
    }
    
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        
        SET_MENU = new int[N+1];
    
        for(int i=1;i<=N;i++)
            SET_MENU[i] = sc.nextInt();
        
        
        dfs(N,0);    // N개의 빵이 남았고, 아무것도 안팔았으니 0원부터 시작.
        System.out.println(MAX_PRICE);
        
    }
 
}
 

조건 추가해서 몇개 더 달았는데도 불구하고 시간초과 공격을 엄청 받았다... 결국 포기하고 DP로 풀었다.

DP문제 풀 때 가장 중요한건, 점화식을 먼저 세우는 것이다! 세상사람 다 알지만 맨날 혼자 까먹는 이 멍청함... 

DP로 풀어야 하는데, 내가 풀어본 것들과는 문제가 달랐다. 

예를 들어보면, 기존의 DP들은 대부분 DP[N-1] + N번째 조건 하면 풀렸는데, 이거는 붕어빵이 4개 남은 경우, 2개 + 2개 일때도 따져줘야 된다는 점.

잘 생각해보면, 2개 + 2개 도 DP[2] + SET_MENU[2]가 되는거고

1개 + 3개 도 DP[1] + SET_MENU[3]이 된다는 점...! 그럭타. 2중 포문을 써야한다!! 

그럼 저 세 가지 경우와 비교할 비교 대상은 누가 되느냐? 위에선 붕어빵 4개로 했으니까 DP[4]가 되시겠다. 

처음에 보고 런타임 에러 날거라고 생각 했는데, 아니더라... 이런 종류의 문제를 많이 풀어보고 생각을 넓혀야겠다!!

[Code]

public class boj_11052_boong_a_bbang {
    
    public static int MAX (int a,int b) {
        return a > b ? a : b;
    }
    
    public static void main(String args[]) {
        
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int SET_MENU[] = new int[N+1];
        int DP[] = new int[N+1];    // DP[i]는 붕어빵이 i개 남았을 때, 최대 이익을 의미한다.
        
        for(int i=1;i<=N;i++)
            SET_MENU[i] = sc.nextInt();    // 각 세트 메뉴 가격을 입력 받는다.
        
        DP[1] = SET_MENU[1];    // 붕어빵 한 개 남았으면 어차피 한개만 팔아야 최대 수익임.
        
        for(int i=2;i<=N;i++)
            for(int j=1;j<=i;j++)
                DP[i] = MAX(DP[i],DP[i-j]+SET_MENU[j]);
        
        System.out.println(DP[N]);
    }
 
}