백준 2662번 기업투자

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

최대 이익과 함께 각 회사에 얼만큼 투자를 했는지를 구해야하는 문제였기 때문에 조금 까다로웠던 문제였습니다.

최대 이익을 구하는 것은 쉬웠습니다.

언제나처럼 종만북 스타일로 재귀함수를 작성하여 각 회사마다 (0~현재 보유하고 있는 금액)만큼 투자를 진행하면서 최대 이익을 구했습니다.

각 회사에 투자한 금액을 구하는 방법은 아래와 같습니다.

1. 다음 회사에 money만큼 투자했을 때 현재 기대하고 있는 최대이익(result)보다 큰 이익이 산출되면 result를 갱신하고 invested[investMoney][companyNum]에 투자한 금액인 money를 저장합니다.

2. 1부터 M까지의 회사를 순회하면서 invested[현재 보유하고 있는 투자금액][회사 번호]를 출력하고 현재 보유하고 있는 투자금액을 갱신해줍니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 300 + 1;

 

int N, M;

int company[MAX][20 + 1]; //투자금, 회사번호

int cache[MAX][20 + 1];

int invested[MAX][20 + 1]; //얼만큼 투자를 했는가

 

int maxOutcome(int investMoney, int companyNum)

{

        //기저 사례

        if (companyNum > M)

                 return 0;

       

        int &result = cache[investMoney][companyNum];

        if (result != -1)

                 return result;

 

        result = 0;

        //한 회사에만 올인할 경우도 있으니 0부터

        for (int money = 0; money <= investMoney; money++)

        {

                 //우선 해당 회사에 money만큼 투자했을 떄 성과금을 temp에 저장

                 int temp = company[money][companyNum] + maxOutcome(investMoney - money, companyNum + 1);

                 if (result < temp) //temp가 현재 기대하는 성과금보다 클 때마다 기록

                 {

                         result = temp;

                         invested[investMoney][companyNum] = money;

                 }

        }

       

        return result;

}

 

//각 회사당 얼만큼 투자했는지 출력

void howMuch(void)

{

        int totalInvest = N;

 

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

        {

                 cout << invested[totalInvest][i] << " ";

                 totalInvest -= invested[totalInvest][i];

        }

        cout << endl;

}

 

int main(void)

{

        cin >> N >> M;

 

        for (int i = 0; i < N; i++)

        {

                 int invest;

                 cin >> invest;

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

                 {

                         int outcome;

                         cin >> outcome;

                         company[invest][j] = outcome;

                 }

        }

       

        memset(cache, -1, sizeof(cache));

 

        cout << maxOutcome(N, 1) << endl;

        howMuch();

 

        return 0;

}

개발환경:Visual Studio 2017

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