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이네요.
일반화 하겠습니다.
i는 1~n까지, j는 1~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; } |
'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 |