백준 [14501] 퇴사

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

14501번: 퇴사

 

	#include<iostream>
	#include<algorithm>
	using namespace std;
	int T[16];//걸리는 기간
	int P[16];//받을 수 있는 금액
	int dp[16];
	int cur_max = 0;
	int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N, t, p;
	cin >> N;
	for (int i = 1; i <= N; i++) {
	cin >> t >> p;
	T[i] = t;
	P[i] = p;
	}
	//N+1일째 퇴사를 하므로 N일동안 상담 후 N+1에 돈받기 가능
	for (int i = 1; i <= N + 1; i++) {
	cur_max = max(cur_max, dp[i]);
	if (i + T[i] > N + 1) continue;
	dp[i + T[i]] = max(dp[i + T[i]], cur_max + P[i]);
	}
	cout << cur_max << '\n';
	return 0;
	}

view raw 14501.cpp hosted with ❤ by GitHub

dp

이미 저장되어 있는 값과(현재 날짜에서 상담을 하지 않는 경우), 현재 날짜에서 상담을 하여 저장되는 값 중 큰 값을 저장해주면 된다.

cur_max  변수를 사용한 이유

-> 예를 들어 7일에 저장된 값이 60이고 그 값이 그대로 간다면 8일에 저장된 값도 60이어야 하는데, 초기값은 0이니까 대입해주는 작업 필요해서 cur_max 변수를 사용한 것