백준 14501번 _ 퇴사

2020-04-25 · 배운 것 · 2분 읽기

https://www.acmicpc.net/problem/14501

14501번: 퇴사

풀이방법

일반적인 dp풀이다.
1. dp[i] = max (dp[i], dp[i-1])
2. dp[i + t[i]] = max (dp[i + t[i]], dp[i]+p[i])

주의사항

마지막날이 1일동안 일하는 날일수 있으므로 dp[N], dp[N+1] 중에서 큰수를 출력해야함.

전체코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int dp[16];
int T[16];
int P[16];
int N;

void Input()
{
	cin >> N;
	int t, p;
	for (int i = 1; i <= N; i++)
	{
		cin >> t >> p;
		T[i] = t;
		P[i] = p;
	}
}

bool inRange(int value)
{
	if (1 <= value && value <= N+1)
		return true;
	return false;
}

void solve()
{
	for (int i = 1; i <= N; i++)
	{
		//1.
		dp[i] = max(dp[i], dp[i - 1]);

		//2.
		int idx = i + T[i];
		if (inRange(idx) == false)
			continue;

		dp[idx] = max(dp[idx], P[i] + dp[i]);
	}

	cout << max(dp[N], dp[N+1]);
}

int main()
{
	Input();
	solve();
	return 0;
}