[동적계획법, 난이도 중] 백준 14501번 퇴사

회사에서 매일 회의가 열리고 각 회의의 기간과 받는 금액이 주어졌을 때, 최대 수익을 계산하는 문제이다.

각 Day마다 열리는 회의가 끝난 후 새로 시작할 수 있는 날을 기록해두고, 현재 Day를 기준으로 이미 끝나 있는 회의 중에서 누적 최대 수익이 큰 경우를 고른 뒤에, 현재 날짜의 회의를 진행하는 식으로 접근하면 된다.

 

아래 표를 보면 이해가 더 잘될 것이다.

S0은 각 Day마다 현재 날짜에 회의 기간을 더한 값들이고, 회의가 끝난 날+1 = 새로 시작할 수 있는 날을 의미한다.

1일차의 경우에는 3일에 걸쳐 회의가 진행되므로 4일차에 새로운 회의를 시작할 수 있다.

즉, S0[1]=4 가 된다.

 

이런식으로 S0는 쉽게 계산 할 수 있고, S1에 해당하는 DP는 2일차 때부터 진행하면 된다.

현재 Day가 되기 전까지 끝낼 수 있는 회의가 있는 날 중에서 최대 누적 수익의 최댓값을 계산하여, 그 최댓값에 현재 Day의 비용을 더한 값을 현재 Day의 S1값으로 정하면 된다.

ex) Day5일 때를 예로 들어보면, 1일,3일,4일에 열리는 회의들은 Day5가 되기 전에 끝난다. 이 중 4일에 여는 회의까지 참석한다면 30만큼의 비용까지 받을 수 있고, 거기에다가 Day5에 여는 회의까지 참석한다면 45만큼의 비용을 받을 수 있다.

퇴사 이전까지 회의를 마칠 수 있는 날들 중, 누적 최대 수익의 최댓값이 이 문제가 원하는 출력값이다.

 

#include <iostream>
using namespace std;
int save[16][2];
int input[16][2];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i < n + 1; i++) {
		cin >> input[i][0] >> input[i][1];
	}
    
        //1일차 처리, 퇴사하는 날을 넘어 회의가 지속된다면 비용을 0으로 한다.
	if (1 + input[1][0] > (n+1)) {
		save[1][0] = 0;
		save[1][1] = 0;
	}
	else {
		save[1][0] = 1 + input[1][0];
		save[1][1] = input[1][1];
	}
	for (int i = 2; i < n + 1; i++) {
		int maxi = 0;
		for (int j = 1; j < i; j++) {
			if (save[j][0] <= i && save[j][1]>maxi) {
				maxi = save[j][1];
			}
		}
		save[i][0] = i + input[i][0];
		save[i][1] = maxi + input[i][1];
	}
	int base = 0;
	for (int i = 1; i < n + 1; i++) {
		if (save[i][0] <= (n+1) && save[i][1] > base) base = save[i][1];
	} 
	cout << base;
}

 

+ 2021-10-14 백준 숏코딩 상위1.9% C++

#include <iostream>
#include <algorithm>
using namespace std;
int d[16],t[16],p[16];
int n,a;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>t[i]>>p[i];
		if(i+t[i]-1>n)continue;
		for(int j=0;j<i;j++)if(j+t[j]<=i)d[i]=max(d[i],d[j]+p[i]);
		a=max(a,d[i]);
	}
	cout<<a;	
}