[알고리즘] 백준14501 퇴사문제 C++

이런 입력이 주어질때는 input.txt 를 만들고 하는 편이다 

수고로움도 덜어주고 시간도 절약되기 때문

 

#include <iostream>
#include <algorithm> //max함수 사용 위해
using namespace std;

struct Item {
    int t;
    int p;
};

#define MAX_N 15 //N 최대값
int n; //입력받을 데이터 수  
int dp[MAX_N+1];
Item item[MAX_N+1];

void sol();

int main(void) {

    //freopen("input.txt","r",stdin);

    cin >> n;
    
    //데이터 입력
    for(int i=1; i<=n ;i++) {
        cin>> item[i].t >> item[i].p;
       // cout << item[i].t<< " , "<< item[i].p <<endl;
        dp[i]=item[i].p;
    }
    sol();

}


void sol(){

    int maxprofit=0;
    for(int i=2;i<=n;i++){
        for(int j=1; j<i ; j++) {
            if(i-j >= item[j].t){
                dp[i] = max( dp[i], dp[j]+item[i].p);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (i + item[i].t <= n + 1) {
            if (maxprofit < dp[i]) {
                maxprofit = dp[i];
            }
        }
    }
    cout << maxprofit <<endl;
}

 

시간이 너무 많이 걸렸다 

 

많이 풀어봐야지