백준] 14501 - 퇴사

시간 제한 : 2초

메모리 제한 : 512MB

입력

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

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

출력

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

소스코드

#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
	pair<int, int> arr[16] = { {0,0}, };
	int dp[16] = { 0, }, n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i].first >> arr[i].second;

	for (int i = 0; i < n; i++)
	{
		if (dp[i] > dp[i + 1])
			dp[i + 1] = dp[i];
		if (dp[i + arr[i].first] < dp[i] + arr[i].second)
			dp[i + arr[i].first] = dp[i] + arr[i].second;
	}
	cout << dp[n];
}

Tip

DP로 풀면 되는데, 초반 접근을 잘못해서 고생을 많이 했다. 막상 식을 세우고 보면 간단한 문제.