[백준 15486번] 퇴사 2 (C++)

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

15486번: 퇴사 2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, maxV;
int arr[1500001][2];
int dp[1500001];

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

    for(int i=0; i<N; i++)
    {
        cin >> arr[i][0] >> arr[i][1]; //날짜, 돈
    }

    for(int i=0; i<=N; i++)
    {
        maxV = max(maxV, dp[i]);
        if(i + arr[i][0] > N) continue; //범위 예외처리
        dp[i+arr[i][0]] = max(maxV + arr[i][1], dp[i+arr[i][0]]); //다음 위치 값 저장
    }
    
    cout << maxV;
}

 

먼저 2차원 배열이나 pair등을 이용하여 날짜와 돈을 순차적으로 입력받아준다.

그리고 현재 날짜 + 현재 날짜의 소요일의 값이 N을 넘어가면 작업이 불가하므로 이 경우를 예외처리해준다.

 

다음으로 현재 날짜 + 현재 날짜의 소요일에 그전까지의 최대값 + 현재 날짜의 돈 or 원래 있던 값 (현재 날짜 + 현재 날짜의 소요일)의 값을 비교하여 큰 값을 넣어준다.

이를 반복하여 값을 넣어주고, 가장 큰 값을 저장해주는 maxV를 출력해주면된다.

여기서 주의해야할 것은 반복문을 보면 i<N이 아닌 i<=N까지를 하였는데, 이는 maxV에 올바른 최대값을 저장하기 위함이다.

max는 dp[0~N-1]까지만 체크하는데 계산에 따라 dp[N]에 값 갱신이 이루어지기 때문에 마지막으로 체크를 한번 더 해준다.

 

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

i = 0
maxV = (maxV, dp[0]) : 0
dp[0+arr[0][0]] -> dp[3]
dp[3] = max(0+10, dp[3]) : 10

i = 1
maxV = (maxV, dp[1]) : 0
dp[1+arr[1][0]] -> dp[6]
dp[6] = max(0+20, dp[6]) : 20

i = 2
maxV = (maxV, dp[2]) : 0
dp[2+arr[2][0]] -> dp[3]
dp[3] = max(0+10, dp[3]) : 10

i = 3
maxV = (mav, dp[3]) : 10
dp[3+arr[3][0]] -> dp[4]
dp[4] = max(10+20, dp[4]) : 30

i = 4
maxV = (maxV, dp[4]) : 30
dp[4+arr[4][0]] -> dp[6]
dp[6] = max(30+15, dp[6](20)) : 45

.
.
.
.
.
.