[알고리즘_PS] boj 15486 퇴사 2 by Cpp

문제

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[1500100] = {
    0,
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    int section_max = 0;
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        int time, pay;
        cin >> time >> pay;
        dp[i + time - 1] = max(section_max + pay, dp[i + time - 1]);
        if (dp[i] > section_max)
            section_max = dp[i];
    }

    int max = *max_element(dp, dp + n + 1);
    cout << max;

    return 0;
}

---

풀이

오랜만에 푼 골드 ~~ 알듯말듯 하다 문제를 차분히 분석했더니 잘 풀려서 풀면서 기분 좋았던 문제 ㅎㅎ

 

dp[i]에는 i일차에 벌 수 있는 가장 큰 금액이 들어간다.

 

time에는 상담을 완료하는데 걸리는 기간, pay에는 상담 완료 시 받을 수 있는 금액이 들어가고, section_max에는 i일 전의 최대 수익을 저장해 놓는다.

 

날짜 진행 순서대로 dp 테이블을 만들어나간다. 단, dp[i]부터 채우는 게 아니라 dp[i+time-1]부터 채워나가는데, 그날 상담 스케줄을 받는다면 i+time-1일에 돈을 받기 때문이다. 이 dp[i+time-1]에는 section_max + pay와 기존의 dp[i+time-1]을 비교해 큰 값을 넣는다. 이렇게 dp 테이블을 채워나가다 보면 i+time-1이 n보다 커지는 경우가 있는데, max_element로 값을 구할 때 범위를 n일 까지로 제한하면 큰 문제없이 풀이가 가능하다.

아래는 이해를 돕기위한 백준 예제1 분석 !

그런데 쓰다보니 생각한게, 5일이나 7일차에 최대 금액을 0원으로 해놓으면 뭔가 이상해서 이 부분을 어떻게 채울지도 생각해봐야겠다.. 내 풀이는 딱 백준 풀이만 생각한 느낌 ㅎㅎ;