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

Posted by 돼지로운생활
2018.01.19 19:52 개발자의 길/알고리즘
 


다이나믹 프로그래밍을 이용해서 풀어낼 수 있는 문제.
dp[n] = n개의 붕어빵을 팔았을 때 얻을 수 있는 최대 이익.
 
X명의 사람에게 붕어빵 [ N ]개를 팔아야 한다. 맨 처음 사람에게 [ i ]개의 붕어빵을 팔았다고 하면 X-1명의 사람들에게는 [ N-i ]개의 붕어빵을 팔아야 한다.
(사람의 수 X는 중요하지 않다. 어차피 다 팔린다고 가정을 하고 풀기 때문. 이해하기 쉽도록 X명이 있다고 표현)
 
점화식으로 풀어보자.
dp[N] = max( p[i] + dp[N-i] , dp[N] )
 
N개를 한번에 다 파는 경우가 가장 비쌀 수도 있기 때문에, max를 이용해서 최대값을 뽑아낸다.
 
< 코드작성 >
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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]);
        
    }
cs

< 출력결과 >

- 문제 예제 출력 결과



- 실제 출력 결과


 






유용한 IT정보 / 전자제품 리뷰
포털에서 MilkyeWay를 검색해주세요👍
유용한 정보였다면 ❤️ 클릭 부탁드려요 😄

이 댓글을 비밀 댓글로