[DP]백준 11052 - 붕어빵 판매하기

붕어빵 판매하기 - 링크

 

다이나믹 프로그래밍을 이용해서 풀어낼 수 있는 문제.

dp[n] = n개의 붕어빵을 팔았을 때 얻을 수 있는 최대 이익.

 

X명의 사람에게 붕어빵 [ N ]개를 팔아야 한다. 맨 처음 사람에게 [ i ]개의 붕어빵을 팔았다고 하면 X-1명의 사람들에게는 [ N-i ]개의 붕어빵을 팔아야 한다.

(사람의 수 X는 중요하지 않다. 어차피 다 팔린다고 가정을 하고 풀기 때문. 이해하기 쉽도록 X명이 있다고 표현)

 

점화식으로 풀어보자.

dp[N] = max( p[i] + dp[N-i] , dp[N] )

 

N개를 한번에 다 파는 경우가 가장 비쌀 수도 있기 때문에, max를 이용해서 최대값을 뽑아낸다.

 

< 코드작성 >

import java.util.Scanner;
 
public class test {
    
    public static void main(String args[]) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        int[] p = new int[n+1];
        
        for (int i=1; i<=n; i++) {
            p[i] = sc.nextInt();
        }
        
        
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=i; j++) {
                dp[i] = Math.max(p[j] + dp[i-j], dp[i]);
            }
        }
        
        System.out.println(dp[n]);
        
    }

< 출력결과 >

- 문제 예제 출력 결과

- 실제 출력 결과