백준 14501 퇴사 풀이

사용언어

Visual studio 2019 C++

유형

다이나믹 프로그래밍

생각하기

간단한 knapsack 문제인듯 .. ??

한가지 주의점이라면 꼭 그 날짜에서 더해서 최대값이 되지 않는 경우도 있다..

10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50

정답 출력: 90
잘못될 경우: 80

[14501 풀이]

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

#define endl "\n"
using namespace std;

int N;
int arr[16];

int main() {
	cin >> N;

	int MAXs = 0;
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		if (i + a > N)
			continue;
		else {
			for (int j = 0; j <= i; j++) {
				arr[i + a] = max(arr[i + a], arr[j] + b);
			}
			MAXs = max(arr[i + a], MAXs);
		}
	}

	cout << MAXs << endl;
}

감동적인 부분은… 4월에는 못풀었는데.. 지금은 아무생각없이 풀어따…

너무 감동적……. 눙물눙물T^T ♥