백준 11052번 붕어빵 판매하기

문제 링크입니다: https://www.acmicpc.net/problem/11052

'(i-j)개 세트 팔았을 때 최대값 + j개 세트 가격' 이 부분이 핵심이였습니다.

/*

강남역에서 붕어빵 장사를 하고 있는 해빈이는 지금 붕어빵이 N개 남았다.

해빈이는 적절히 붕어빵 세트 메뉴를 구성해서 붕어빵을 팔아서 얻을 수 있는 수익을 최대로 만드려고 한다.

붕어빵 세트 메뉴는 붕어빵을 묶어서 파는 것을 의미하고, 세트 메뉴의 가격은 이미 정해져 있다.

붕어빵 i개로 이루어진 세트 메뉴의 가격은 Pi 원이다.

붕어빵이 4개 남아 있고, 1개 팔 때의 가격이 1, 2개는 5, 3개는 6, 4개는 7인 경우에 해빈이가 얻을 수 있는 최대 수익은 10원이다.

2개, 2개로 붕어빵을 팔면 되기 때문이다.

1개 팔 때의 가격이 5, 2개는 2, 3개는 8, 4개는 10 인 경우에는 20이 된다.

1개, 1개, 1개, 1개로 붕어빵을 팔면 되기 때문이다.

마지막으로, 1개 팔 때의 가격이 3, 2개는 5, 3개는 15, 4개는 16인 경우에는 정답은 18이다.

붕어빵을 3개, 1개로 팔면 되기 때문이다.

세트 메뉴의 가격이 주어졌을 때, 해빈이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

*/

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

int setPrice[1001]; //개당 세트 가격

int breadNum; //붕어빵 갯수

int cache[1001];

 

int maxPrice(void)

{

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

        {

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

                       //(i-j)개 세트 팔았을 때 최대값 + j개 세트 가격

                       cache[i] = max(cache[i], cache[i - j] + setPrice[j]);

        }

        return cache[breadNum];

}

 

int main(void)

{

        cin >> breadNum;

 

        memset(cache, 0, sizeof(cache));

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

               cin >> setPrice[i];

 

        cout << maxPrice() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~