[백준] 14501번 퇴사 - C/C++ (Easy 풀이)

백준 14501 문제(Problem)

 

백준 14501 문제

 

입력

 

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

 

 

풀이 & 전체 코드(Solution & Code)

#include<iostream>
#include<algorithm>
using namespace std;
int n, t[1002], p[1002], dp[1002];

int main() {
	// 남은 일 수 N 입력
	cin >> n;
	// N일 동안의 상담 시간(t)과 수익(p) 입력
	for(int i=0; i<n; i++)
		cin >> t[i] >> p[i];

	// 뒤에서부터 동적 계획법을 사용하여 최대 수익 계산
	for(int i=n-1; i>=0; i--) {
		int pos=i+t[i]; // 해당 날짜에서 상담이 끝나는 위치 계산
		if(pos<=n)
			dp[i]=max(dp[pos]+p[i], dp[i+1]); // 해당 날짜에서 상담을 할 경우와 안 할 경우 중 최대 수익 선택
		else
			dp[i]=dp[i+1]; // 해당 날짜에서 상담을 할 수 없는 경우 다음 날의 최대 수익을 그대로 사용
	}
	// 최대 수익 출력
	cout << dp[0];
}