[백준][C++] 15486번: 퇴사 2 <238>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

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

15486번: 퇴사 2

 

생각의 흐름

N의 범위가 150만 이라서 완전탐색 이런 방식으로는 절대 해결할수 없다 생각하였다.

그리고 문제 자체에서 DP smell이 엄청나게 느껴졌다. 바로 동적계획법을 적용시켜보려 노력하였다.

 

우리는 문제의 예시 1번을 통해서 생각해봅시다!

우선 DP[i]의 의미를 다음과 같이 정하였습니다

DP[i]이라는 것은 "i일 전까지 일을 해서 벌 수 있는 최대 액수"를 의미한다.

 

왜 전까지 일한 금액일까? 만약 1일부터 3일치를 일하면 4일날 10을 받을 수 있기 때문이다.

 

그럼 우리는 1일을 계산하면서 DP[4]의 값을 10으로 갱신할 수 있다.

	1일	2일	3일	4일	5일	6일	7일
DP[i]	0	0	0	10	0	0	0

 

2일로 가보자. 현재 2일까지 일을 해서 벌 수 있는 최대 금액은 0원이다.

2일날 일을 하면 돈을 7일날 받게 될 것이다. 즉, DP[7] = 20 이라고 우리는 갱신할 수 있다.

	1일	2일	3일	4일	5일	6일	7일
DP[i]	0	0	0	10	0	0	20

 

3일로 가보자. 현재 3일까지 일을 해서 벌 수 있는 최대 금액은 0원이다. 3일날 일을 하면 4일날 받게 될 것이다.

 

현재 DP[4]가 10인 상황이다.

하지만, '3일'날 일을 한다고해서 10원보다 더 큰 액수를 벌 수 있는 것은 아니므로 그대로 DP[4] = 10으로 유지될 것이다.

	1일	2일	3일	4일	5일	6일	7일
DP[i]	0	0	0	10	0	0	20

  

4일로 가보자. 현재 DP[4]는 10인 상황이다.

4일날 일을 하게 되면 5일날 받게 될 것이다. DP[5]의 최대 액수는 얼마일까 ?

둘 중 하나일 것이다.

   1. 4일까지 일을 해서 벌 수 있는 최대 액수 + 4일날 일을 함으로써 벌 수 있는 돈

   2. 기존에 설정된 5일까지 일을 해서 벌 수 있는 최대액수

 

1번 같은 경우, DP[4] + 4일날 일을 함으로써 벌 수 있는 20 => 30원이 될 것이고, 2번 같은 경우 아직 5일은 벌 수 있는 돈이 없으므로 0원일 것이다. 즉, DP[5] = 30으로 갱신될 것이다.

	1일	2일	3일	4일	5일	6일	7일
DP[i]	0	0	0	10	30	0	20

 

위와 같은 방식으로 탐색을 해주면 된다. 단, 일을 함으로써 받게 되는 돈의 날짜가 N + 1 보다 커져버리면 그 일은 할 수 없다.

 

 

나의 코드

#include <bits/stdc++.h>
#include <iostream>

using namespace std;
#define MAX 1500001

int DP[MAX];

int N;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    vector<pair<int, int>> vec;

    vec.push_back({0, 0});
    int day, cost;
    for(int i = 0; i < N; i++) {
        cin >> day >> cost;
        vec.push_back({day, cost});
    }

    int currentMax = 0;
    for(int i = 1; i <= N+1; i++) {
        currentMax = max(currentMax, DP[i]);
        if(i + vec[i].first > N+1) continue;
        DP[i + vec[i].first] = max(DP[i + vec[i].first], currentMax + vec[i].second);
    }

    cout << currentMax;

    return 0;
}