[BOJ] 11052 - 붕어빵 판매하기

1. 알고리즘

DP문제

2. 전체 소스

#include <iostream> #include <vector> using namespace std; int main() { int arr[1001] = { 0, }; int num; int max; cin >> num; vector <int> v(num); for (int i = 0; i < num; i++) { cin >> v[i]; } for (int i = 1; i <= num; i++) { max = 0; for (int j = 0; j < i; j++) { arr[i] = arr[j] + v[i - j - 1]; if (arr[i] > max) max = arr[i]; } arr[i] = max; } cout << max << endl; return 0; }

4
1 5 6 7 일 경우를 예로들면,

int arr[1001] = { 0, };

arr 배열에는 각각 n개 붕어빵을 팔 때 가장 비싸게 팔 수 있는 값을 넣을 것이다.
arr[0] 은 n=0으로, 0개의 붕어빵을 팔았을때 값이므로 0으로 초기화 하였다. 

for (int i = 1; i <= num; i++) { max = 0; for (int j = 0; j < i; j++) { arr[i] = arr[j] + v[i - j - 1]; if (arr[i] > max) max = arr[i]; } arr[i] = max; }

arr[1] = arr[0] + v[0];
1) 붕어빵 1개를 팔았을 때 
Case 1 : 0개를 팔았을 때 + 1개의 가격 => arr[1] = 1 
arr[1] = 1

arr[2] = arr[0] + v[1];
arr[2] = arr[1] + v[0];
2) 붕어빵 2개를 팔았을 때
Case 1 : 1개을 팔았을 때 + 1개  => arr[2] = 2
Case 2 : 2세트를 판다. (=0개를 팔았을 때 + 2개를 더 팔면 된다.) => arr[2] = 5
Case 1과 Case2 중에서 더 큰 값을 배열에 저장한다.
arr[2] = 5

arr[3] = arr[0] + v[2];
arr[3] = arr[1] + v[1];
arr[3] = arr[2] + v[0];
3) 붕어빵 3개를 팔았을 때 
Case 1 : 1개 팔았을 때 + 2개를 더 팔면된다. => arr[3] = 6
Case 2 : 2개 팔았을 때 + 1개를 더 팔면된다. => arr[3] = 6
Case 3 : 3세트를 판다. (=0개를 팔았을 때 3개를 더 팔면 된다.) =>  arr[3] = 6
Case 1과 Case2, Case3 중에서 더 큰 값을 배열에 저장한다.
arr[3] = 6

arr[4] = arr[0] + v[3];
arr[4] = arr[1] + v[2];
arr[4] = arr[2] + v[1];
arr[4] = arr[3] + v[0];
4) 붕어빵 4개를 팔았을 때
Case 1 : 1개를 팔았을 때 + 3개를 더 팔면 된다 => arr[4] = 8
Case 2 : 2개를 팔았을 때 + 2개를 더 팔면 된다 => arr[4] = 10
Case 3 : 3개를 팔았을 때 + 1개를 더 팔면 된다 => arr[4] = 8
Case 4 : 4세트를 판다. (=0개를 팔았을 때 4개를 더 팔면 된다.) => arr[4] = 7
Case 1과 Case2, Case3, Case4 중에서 더 큰 값을 배열에 저장한다.
arr[4] = 10

3. 참고 사항

if (arr[i] > max) max = arr[i];

위 소스 대신에

#include <algorithm> max = max(arr[i], max);

max함수를 사용했을때는 결과로 컴파일 에러가 떴다.  (c++ 11)
원인은 뭔지 모르겠다.

4. 문제

백준 알고리즘 : https://www.acmicpc.net/problem/11052