PS/BOJ

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

Jubil 2018. 6. 2. 16:29
반응형

11052_붕어빵 판매하기

 

링크

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

 

풀이


 

 

붕어빵을 N개 팔아서 얻을 수 있는 최대 이익을 DP[N]이라고 정의하고, 붕어빵 N개 팔 때의 가격을 P[N]이라고 정의하겠습니다.

그리고 DP는 모두 0으로 초기화 하겠습니다.

 

 

위의

1 5 6 7 의 예제로 설명하겠습니다.


 

붕어빵 1개를 팔아야 한다면 D[1-1] + P[1] 하나뿐입니다.

참고로 DP[1-1] + P[1]1-1개 팔 때 최대 이익 + 1개 팔 때의 가격입니다.


 

붕어빵 2개를 팔아야 한다면

DP[2-1] + P[1]

DP[2-2] + P[2]

중에 큰 값이 DP[2]가 될 것입니다.

 

DP[2-1] + P[1]1+1=2, DP[2-2] + P[2]0+5=5입니다.

DP[2] = DP[2-2] + P[2]가 되겠네요.


 

붕어빵 3개를 팔아야 한다면

DP[3-1] + P[1]

DP[3-2] + P[2]

DP[3-3] + P[3]

중에 큰 값이 DP[3]이 될 것입니다.

 

DP[3-1] + P[1]5+1=6, DP[3-2] + P[2]1+5=6, DP[3-3] + P[3]0+6=6입니다.

어쨌든 DP[3]=6이네요.


 

 

마지막입니다.

붕어빵 4개를 팔아야 한다면

DP[4-1] + P[1]

DP[4-2] + P[2]

DP[4-3] + P[3]

DP[4-4] + P[4]

중에 큰 값이 DP[4]가 될 것입니다.

 

DP[4-1] + P[1]6+1=7, DP[4-2] + P[2]5+5=10, DP[4-3] + P[3]1+6=7, DP[4-4] + P[4]0+7=7입니다.

DP[4], 4개의 붕어빵을 팔 때, 최대로 얻을 수 있는 이득은 10이네요.


 

 

일반화 하겠습니다.

i1~n까지, j1~j까지 for문을 돌려줍니다.

DP[i] = MAX(DP[i-j] + P[j], DP[i]); 을 사용해서 DP[i]를 구해줍니다.

 

 

코드

 

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

27

28

29

//11052_붕어빵 판매하기

#include <iostream>

using namespace std;

 

int DP[1001], P[1001];

 

int MAX(int a, int b){

    return a > b ? a : b;

}

 

int main(){

    int n;

    int i, j;

 

    cin >> n;

 

    for (i = 1; i <= n; ++i)

        cin >> P[i];

 

    for (i = 1; i <= n; ++i){

        for (j = 1; j <= i; ++j){

            DP[i] = MAX(DP[i-j] + P[j], DP[i]);

        }

    }

 

    cout << DP[n] << endl;

 

    return 0;

}

Colored by Color Scripter

cs

 

 



반응형

'PS > BOJ' 카테고리의 다른 글

[백준 BOJ][DP] 2156 포도주 시식  (0) 2018.06.03
[백준 BOJ][DP] 1463 1로 만들기  (1) 2018.06.03
[백준 BOJ][DP] 11057 오르막 수  (0) 2018.06.02
[백준 BOJ][DP] 1912 연속합  (0) 2018.06.02
[백준 BOJ][DP] 2193 이친수  (5) 2018.06.02