[백준/Baekjoon] 14501 퇴사 C++ :: Dynamic Programming

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

14501번: 퇴사

---

1. Logic

- 처음엔 dp테이블을 2차원이라고 생각했지만 인덱스 갯수가 1500000이기 때문에 dp table이 2개가 아닌 한개라고 생각했다.

- 부분문제를 쪼개봤다

1. 해당 날짜의 상담을 할때

 - idx + 상담에 필요한 시간 + 상담으로 받은 상담비용

2. 해당 날짜의 상담을 안할때

 - 상담을 안하고 다음 인덱스로 넘어가기

 

 

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;

vector<pair<int, int>> vec;
int dp[1500001];

int solve(int cur) {
    if(cur == n) return 0;
    int &ret = dp[cur];
    if(ret != -1) return ret;

    ret = 0;

    //상담 할때
    if(cur + vec[cur].first <= n) {
        ret = max(ret, solve(cur + vec[cur].first) + vec[cur].second);
    }
    //안하고 넘어갈때
    ret = max(ret, solve(cur + 1));

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(dp, -1, sizeof(dp));
    cin >> n;

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

    cout << solve(0);
}

 

 

---

3. Feedback

- 한 방법을 생각했다고 계속 그 방법으로 밀고나가지 말고 정 안된다면 다른 방법을 생각해보기

DP테이블을 줄이거나 늘리거나 / value넘기는 방식을 변경하거나