<Baekjoon> #14501 Dynamic Programming_퇴사 c++

#14501 퇴사
참고1 참고2

문제를 보자마자 이건 dp로 풀어야겠다.. 는 알겠는데 그 이후 풀지를 못한다.. dp문제를 많이 풀었는데 아직도 잘 못하냐.. 그냥 열심히 더 풀어보는 수밖에 ㅠㅠ

✍문제 정리

• N일 동안 매일 상담에 필요한 시간과 수익이 하나씩 주어진다
• 예를 들어 1일에 잡혀있는 상담이 3일이고 이 상담을 완료하려면 4일 째부터 다른 상담을 할 수 있다
• 상담을 적절히 했을 때 최대 수익을 구해야 한다

💬Solution 1

• dp[i]를 현재 i번째 날일 때, i번째 날에 들어오는 작업을 포함하여 할 수 있는 최대 작업 이익이라 설정해둔다
• 만약 i번째 날 들어온 작업이 N일 내에 끝낼 수 있는 작업이면 i번째 날에 들어온 작업 이익(pay[i])이 dp[i]에 기본적으로 저장된다
• i번째 날 이전에 끝낼 수 있는 작업이 있다면 이 끝낼 수 있는 작업 이익중 가장 큰 값과 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;
}

💬Solution 2

• 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]이 된다
  
  ① 7일 째, 6일 째 시작한 일은 모두 주어진 날 N=7일 안에 끝낼 수 없기 때문에 dp[6]=dp[7]=0
  
  ② 5일 째 일을 수행하게 되면 6번 째 일은 시작할 수 없다. 따라서 5번째 일을 시작해서 6번 째 일을 못하고 7번 째부터 얻을 수 있는 이익을 더해주는 것과 5번째 일을 하지 않고 6번 째 일부터 얻을 수 있는 이익 중 더 큰 값을 dp[5]에 넣어준다
  
  ③ 4일 째 일을 수행하고 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;
}