[백준 14501번] 퇴사 (C++)

문제링크 : https://www.acmicpc.net/problem/14501

 

#include <bits/stdc++.h> 
using namespace std;

int n;
int t[16], p[16], dp[16] = {0};
int result = 0, sum = 0;
int main()
{
	cin >> n;
	for(int i=1; i<=n; i++)
	{
		cin >> t[i] >> p[i];         //기간과  금액 입력
		for (int j = 0; j < i; j++)  //상담 기간이 현재 i보다 작은 것 찾기
		{
			if (t[j] + j <= i && t[i] + i - 1<= n)  // j일과 j기간의 합이 <=i 일때와, 
			{                                       // i일과 i기간의 합과 중복값 1을 뺀 값이 <=n 일 때
				dp[i] = max(dp[i], dp[j] + p[i]);   //그전까지 저장한 값이 큰가, 새롭게 더한 값이 더 큰가
			}
		}
	}
	sort(dp, dp+16);
	cout << dp[15];  //정렬해서 마지막 값(가장 큰) 출력
	return 0;
}

가장 큰 값은 dp 배열을 정렬하여 마지막 값을 출력했다.