백준 14501번 퇴사

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

알고리즘은 간단합니다. 

해당 일에 배정된 상담을 택하거나 해당 일에 배정된 상담을 택하지 않는 경우의 수만 파악하면 됩니다.

해당 일에 배정된 상담을 택할 경우 해당 상담에 배정된 금액 또한 더해주고 DP를 통해 최대 이익을 찾으면 되는 문제였습니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 15 + 1;

const int INF = 987654321;

 

int N;

pair<int, int> input[MAX];

int cache[MAX];

 

int maxProfit(int day)

{

        //기저 사례: 상담 진행하는 일 수가 N을 초과하면 안 된다

        if (day == N + 1)

                 return 0;

        if (day > N + 1)

                 return -INF;

 

        int &result = cache[day];

        if (result != -1)

                 return result;

 

        result = 0;

        //해당 일 상담을 택할 것인가 다음날 상담으로 넘어갈 것인가

        result += max(input[day].second + maxProfit(day+input[day].first), maxProfit(day + 1));

        return result;

}

 

int main(void)

{

        cin >> N;

 

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

                 cin >> input[i].first >> input[i].second;

 

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

 

        cout << maxProfit(1) << endl;

        return 0;

}

개발환경:Visual Studio 2017

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