[BOJ-14501] 퇴사

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

[문제요약]

퇴사를 하기 위해서 남은 근로일 동안 일을 했을 때 이익을 낼 수 있는 최대치를 구하는 문제이다.

일을 시작하면 시작한 날(1일) 을 포함하여 일한 날을 계산한다. 

일은 동시에 진행할 수 없으며, 하나의 일을 마친 후 일을 할 수 있다.

[입력]

남은 근로일(N~[1, 15])이 주어지고,

날마다 일이 주어졌을 때 처리에 필요한 일 수(Ti~[1, 5]) 그리고 일을 처리했을 때 이익(Pi~[1, 100])을 입력으로 주어진다.

[출력]

최대 이익을 출력한다.

[접근방법]

T[] : 해당 일자에 일을 시작할 때 처리에 필요한 일 수

P[] : 해당 일자에 시작한 일의 수익

D[] : 해당 날에 최대수익

mx : 이전 날짜들 중 최대 수익

최대 수익(mx)을 현재날짜 이전까지 최대 값인 수익으로 갱신한다.

current : 현재날짜

P[current] : 수행에 필요한 일자

D[ current + P[current] ] < mx + P[current] 

그 값들 중 최대값을 출력한다.

[C++11 source Code]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

#include<cstdio> #define din1(a) scanf("%d", &a)   const int M = 22; int T[M]; int P[M]; int D[M]; int ans;   int main() {     int N;     din1(N);     for (int i = 1; i <= N; i++) {         din1(T[i]);         din1(P[i]);     }       for (int i = 1; i <= N+1; i++) {         int mx = 0;         for (int d = 0; d <= i; d++) {             if (mx < D[d])                  mx = D[d];         }         if (D[i + T[i]] < (mx + P[i]) ) {             D[i + T[i]] = mx + P[i];         }           ans = (ans > D[i]) ? ans : D[i];     }       printf("%d", ans);     return 0; } Colored by Color Scripter

cs