[백준] 14501번 퇴사

문제: 14501번: 퇴사

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

 

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	// 0행: 기간, 1행: 가격, 2행: 누적합
	int table[3][17] = { 0 }; // 0번 열은 사용하지 않을 것.. 17까지 범위를 잡은 이유는 인덱스 범위 벗어나는 걸 방지하기 위함
	for (int i = 1; i < n + 1; i++) {
		cin >> table[0][i] >> table[1][i];
	}

	int answer = 0;
	for (int i = 1; i < n + 1; i++) {
		// 이전까지의 최대값 반영
		table[2][i] = max(table[2][i], table[2][i - 1]);

		int day = table[0][i];
		int cost = table[1][i];

		// 상담 가능 일자를 넘으면 걍 건너뛰도록..
		if (i + day > n + 1) continue;

		// 누적합 갱신
		table[2][i + day] = max(table[2][i] + cost, table[2][i+day]);

		// 더 큰 값으로 answer 갱신
		answer = max(answer, table[2][i + day]);
	}
	cout << answer;

	return 0;
}

 

table 배열을 선언해서 0행에는 일수, 1행에는 비용, 2행에는 누적합을 저장했다.

 

1부터 n 까지 for 문을 돌려서 누적합을 계산하도록 했다.

 

for 문에 진입하면 일단 현재 인덱스의 누적합을 현재의 누적합과 이전 인덱스의 누적합을 비교한 후 더 큰 값으로 갱신하도록 했다. 이는 현재까지의 최대값을 반영하기 위함이다.

 

그 다음으로는 i + 일자값을 인덱스로 이용해서 누적합을 계산하도록 했다. table[2][i] + cost (새로운 값), table[2][i+day] (원래 값) 두 값을 비교해서 더 큰 값으로 갱신할 수 있도록 했다.