백준 15486 - 퇴사 2(C++)

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

15486번: 퇴사 2

Dp 문제였습니다.

N+1일에 퇴사를 했을 때, 얻을 수 있는 최대 이익을 구하는 문제입니다.

N의 값이 1,500,000이기에 이중 for문을 사용하면 시간 초과가 됩니다.

따라서 Dp 배열을 이용해, 최댓값을 계속 갱신해주면서, Max 변수를 통해 지금까지의 최댓값을 확인해가면 되는 문제입니다.

 

이때, Dp[X]는 X일까지 포함된 이익이 아니라는 것을 유의하셔야 합니다.

 

문제의 예시를 통해서 점화식을 확인해보겠습니다.

1일에서 얻을 수 있는 수익은 당연히 0입니다. 1일에서 일을 한다면 3일이 걸리고 10의 수익을 얻습니다.

따라서 Dp[4] = 10이 됩니다.

 

2일에서 얻을 수 있는 수익도 0입니다. 2일에서 일을 한다면 5일이 걸리고 20의 수익을 얻습니다.

따라서 Dp[7] = 20이 됩니다.

 

3일에서 얻을 수 있는 수익은 0입니다. 3일에서 일을 한다면 1일이 걸리고 10의 수익을 얻습니다.

이전에 Dp[4]의 값이 저장이 되있기에 3일의 경우와 비교해 최댓값을 저장해 줍니다. 

따라서 Dp[4] = 10이 됩니다.

 

이를 통해 점화식을 구하면, Dp[i+work[i][0]] = max(Max + work[i][1], Dp[i+work[i][0]]) 가 됩니다.

이떄, i+work[i][0]는 N+1을 넘어가면 안됩니다.

 

Max 변수를 사용하는 이유는 N일을 구할 때, N-1의 값이 가장 큰 경우가 아닐 확률이 있기에, 1~N-1까지의 값 중, 가장 큰 값을 저장해야 하기 때문입니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>
#define P pair<int, int>
#define PP pair<P, P>
#define F first
#define S second
#define INF 1000000000

using namespace std;

int work[1500020][2]; // day, cost
int Dp[1500020];
int N;

void solve(){
    int Max = 0;
    for(int i = 1; i <= N+1; i++){
        Max = max(Max, Dp[i]);
        if(i + work[i][0] <= N+1){
            Dp[i+work[i][0]] = max(Max+work[i][1], Dp[i+work[i][0]]);
        }
    }
    cout << Max;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> work[i][0] >> work[i][1];
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요