[백준][삼성 SW 역량 테스트][Silver 4][C++] 14501 퇴사

문제

백준 삼성 SW 역량 테스트 기출 문제 - 14501 퇴사 (Silver 4)

14501번: 퇴사

 

---

문제 풀이

접근 방식

상담을 적절히 했을 때, 얻을 수 있는 최대 수익을 구하는 문제이다.

이 문제는 DP 방식으로 문제를 해결하였다.

 

우선, DP 벡터를 만들어 DP[i]에 i - 1일 동안 했던 상담의 최대 수익을 저장해주었다.

 

i번째 날의 상담을 기간 내에 할 수 있는 경우에는,

DP[i + 소요 기간]에 기존의 값과 (DP[i] + 수익)의 값 중 더 큰 값을 저장해주었다.

또한, 매번 다음날의 값과 현재의 값을 비교하여 더 큰 값을 DP[i+1]에 저장하였다.

 

위의 과정을 주어진 일정만큼 반복하면 DP[N+1]에는 N일 동안 했던 상담의 최대 수익이 저장된다.

 

---

풀이 코드 - C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	// 입력 받기
	int N;
	cin >> N;
	vector<pair<int, int> > works(N+2);
	for (int i = 1; i <= N; i++)
		cin >> works[i].first >> works[i].second;

	// DP
	vector<int> DP(N + 2);
	for (int i = 1; i <= N; i++) {
		// i번째 날에 일을 할 수 있는 경우
		if (i + works[i].first <= N + 1)
			DP[i + works[i].first] = max(DP[i + works[i].first], DP[i] + works[i].second);
		
		DP[i + 1] = max(DP[i + 1], DP[i]);
	}

	cout << DP[N+1];
}

실행 결과

실행 결과 : 통과 (0ms)