문제를 보자마자 이건 dp로 풀어야겠다.. 는 알겠는데 그 이후 풀지를 못한다.. dp문제를 많이 풀었는데 아직도 잘 못하냐.. 그냥 열심히 더 풀어보는 수밖에 ㅠㅠ
dp[i]
를 현재 i번째 날일 때, i번째 날에 들어오는 작업을 포함하여 할 수 있는 최대 작업 이익이라 설정해둔다pay[i]
)이 dp[i]
에 기본적으로 저장된다dp[i]
에 저장한다.i+time[i]<=N+1
: i번째 날 들어온 작업이 시간 내에 끝낼 수 있고, j+time[j]<=i
: 이전 j 번째 날 들어온 작업이 i번째 날 이전에 끝낼 수 있을 때, dp[i]=max(dp[i], dp[j]+pay[i])
전체코드
#include <iostream> #include <cmath> using namespace std; const int MAX = 16; int _time[MAX] = {0}; int pay[MAX] = {0}; int dp[MAX] = { 0 }; /* dp[i]= 현재 시간이 i일 때, i시간에 들어오는 작업을 포함하여 할 수 있는 최대 작업 이익 */ int main() { int N; cin >> N; for (int i = 1; i <= N; i++) { cin >> _time[i] >> pay[i]; for (int j=0; j<i; j++) { if (i + _time[i] <= N + 1 && j + _time[j] <= i) { dp[i] = max(dp[i], dp[j] + pay[i]); } } } int ans = 0; for (int i = 1; i <= N; i++) ans=max(ans, dp[i]); //printf("%d ", dp[i]); return 0; }
i
번째 시작한 일은 i+time[i]-1
번째 날 끝나기 때문에 dp[]
를 끝에서부터 채워본다dp[]
는 모두 0으로 초기화 하고, i
번째 날 주어진 일이 N
보다 초과되면 dp[i]=dp[i+1]
값을 넣어준다 (이때 i=N일 경우 런타임 에러가 안 나게 배열 크기를 잘 조정해준다)i
번째 날 주어진 일이 N
일 안에 끝낼 수 있다면 dp[i]=max(dp[i+time[i]]+pay[i], dp[i+1])
을 수행해준다. 즉 이 말은, i
번 째 일을 수행하면 time[i]
일간 다른 상담은 하지 못하고 pay[i]
의 거래 급액을 받을 수 있고, i
번 째 일을 수행하지 않으면 dp[i+1]
이 된다N=7
일 안에 끝낼 수 없기 때문에 dp[6]=dp[7]=0dp[5]
에 넣어준다4+time[4]=5
일째 부터 얻을 수 있는 이익을 더해주는 것이 4일 째 일을 수행하지 않고 5일 째부터 얻을 수 있는 이익 dp[5]
보다 크다dp[1]
에 있는 값이 총 N일동안 얻을 수 있는 최대 이익이다전체코드
int main() { int N; cin >> N; for (int i = 1; i <= N; i++) cin >> _time[i] >> pay[i]; for (int i = N; i >= 1; i--) { if (i + _time[i] > N + 1) { dp[i] = dp[i + 1]; continue; } dp[i] = max(dp[i + _time[i]] + pay[i], dp[i + 1]); } //for (int i = 1; i <= N; i++) //printf("%d ", dp[i]); cout <<" \n" << dp[1] << endl; return 0; }