[11052번] 붕어빵 판매하기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. BFS

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

        {

            int there = here + i;

 

            if (there > n)

                break;

 

            DP[there] = max(DP[there], DP[here] + menu[i]);

 

            q.push(there);

        }

there은 현재 팔았는 붕어빵 + 세트메뉴의 개수를 의미한다

즉, 현재 2개(here)를 팔았다면

there은 here(2) + 1(i) 총 3개를 판다는 뜻이고 이때 there은 1개짜리 세트를 판다는 의미이다.

there = 2 + 2가되면 4개를 판다는 뜻이고 이미 2개 팔아왔는 상태에서 2개짜리 세트를 판다는 의미이다.

DP[there]은 총 누적 가격을 의미하는데, 이미 there에 존재하는 가격과 here개 팔았을때 최댓값과 i개 세트를 팔았을 때 가격중 최댓값을 의미한다. 

이 문제를 풀고 [1699번] 제곱수의 합 :: https://www.acmicpc.net/problem/1699을 풀어보면 매우 유사하다는 것을 알 수 있다.

소스 코드 : 

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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

#include <cstdio> #include <iostream> #include <queue> #include <algorithm> #include <queue>   using namespace std;   int DP[1001]; int menu[1001]; bool visit[1001]; queue <int> q;   int main() {     int n;     scanf("%d", &n);     for (int i = 1; i <= n; i++)         scanf("%d", &menu[i]);       q.push(0);       while (!q.empty())     {         int here = q.front();           q.pop();                  if (visit[here])             continue;           visit[here] = 1;             for (int i = 1; i <= n; i++)         {             int there = here + i;               if (there > n)                 break;               DP[there] = max(DP[there], DP[here] + menu[i]);               q.push(there);         }     }       printf("%d", DP[n]);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus