퇴사_14501

문제 출처 : 퇴사_14501

DP 문제 풀이

DP 문제는 구현은 쉬운데, 조건문이 까다로움
여러 가지 상황을 생각해서 빈틈이 생기지 않도록 조건문을 짜야할 것 같음
구현 시작 전에 예제를 손으로 풀어보고 특별한 경우가 있는 지 확인하기

파라미터 정리

N 남은 기간, 퇴사는 N+1일 째 되는 날 함 (1~15)
Ti 상담을 완료하는 데 걸리는 시간 (1~5)
Pi 상담 후 받는 금액 (1~100)
상담을 완료하는 기간 Ti 동안은 다른 일을 중복으로 할 수 없음
원하는 것 = 일정이 주어졌을 때 최대 수익을 반환하기

간략한 과정

input_1 N 입력받기
input_2 [Ti Pi]를 N번 입력 받는다. 각 순서는 1일부터 N일 까지를 의미함
Ti는 period[15], Pi는 money[15]에 순차적으로 넣음
누적되는 금액을 나타내는 sum[16]을 만듦
각 상황에서 전월 ~ n월 전에 대한 금액과 현재 금액을 선택했을 때 득실을 고려함
상황마다 최댓값이 되도록 갱신함
output 최종적으로 가장 큰 값인 sum[15]를 출력함

코드

for문 정방향

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<int> period, money;

int solve(){
    int res = 0;
    int sum[15] = {0};
    //거꾸로 돌아가야 함
    for(int i = 0; i < N; i++){
        int np = period.back();
        period.pop_back();
        int nm = money.back();
        money.pop_back();
        int idx = N-1 -i;
        if(idx+np > N) {
            if(i == 0) continue;
            sum[i] = sum[i-1];
            //cout << i << " : " << sum[i] << endl;
            continue;
        }
        //if(np)
        idx = i-(np);
        int curr;
        if(idx < 0) curr = nm;
        else curr = sum[i-np] + nm;
        
        sum[i] = max(sum[i-1], curr);
        cout << i << " : " << sum[i] << endl;
    }
    res = sum[N-1];
    return res;
}

int main()
{
    cin >> N;
    for(int i = 0; i < N; i++){
        int p1, m1;
        cin >> p1 >> m1;
        period.push_back(p1);
        money.push_back(m1);
    }
    cout << solve() << endl;

    return 0;
}

for문 역방향

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<int> Time;
vector<int> Price;

int solve(){
    int sum[16] = {0};
    int size = Time.size();
    for(int i = size-1; i >= 0; i--){
        int date = Time.back();
        Time.pop_back();
        int cost = Price.back();
        Price.pop_back();
        if(date+i <= N){
            int temp = sum[i+date]+cost;
            sum[i] = max(temp,sum[i+1]);
        }else{
            sum[i] = sum[i+1];
        }
    }
    
    return sum[0];
}

int main()
{
    cin >> N;
    for(int i = 0; i < N; i++){
        int t,p;
        cin >> t >> p;
        Time.push_back(t);
        Price.push_back(p);
    }
    cout << solve() << endl;

    return 0;
}