[BOJ/C++] 14501 퇴사

채린·2024년 10월 10일
1

퇴사

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    int N;
    cin>>N;
    vector <vector<pair<int,int>>> vec(N+1);// i날 끝나는거 모음:시작 날짜, 금액
    vector<int> dp(N+1);
    
    int t,p;
    for(int i=1;i<=N;i++){
        cin>>t>>p;
        if (i + t - 1 <= N) vec[i+t-1].push_back(make_pair(i,p));
    }
    
    for(int i=1;i<=N;i++){
        dp[i]=dp[i-1];
        for(pair<int,int> p : vec[i]){
            dp[i]=max(dp[i],dp[p.first-1]+p.second);
        }
    }
    
    cout<<dp[N];

    return 0;
}
  1. if (i + t - 1 <= N) 이거 추가 안하고서 왜 코드 안돌아가징.. 이랬다..
  2. dp 식에서 dp[p.first-1]+p.second인데 처음엔 dp[p.first]+p.second로 작성했다,,
  3. 식: 현재 i일에서 끝나는 모든 상담에 대해 진행
    start: 현재 보고있는 상담이 시작하는 날 / p: 현재 보고있는 상담의 금액
    dp[i]=max(dp[i-1]+dp[start-1]+p)

0개의 댓글