[BAEKJOON] 14501번 퇴사

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

14501번: 퇴사

문제조건

1. 퇴사 전까지 상담을해서 얻을수 있는 최대 수익을 구하라

단순히 구현 + dp 문제였다.

dp[i] : i일까지의 상담중에서 최대 수익 값

완전탐색을 진행하면서 상담에 걸리는 일수가 퇴사 전일때, 구하고자 하는 일자의 수익과, 지금까지의 수익 + 구하고자 하는 일자까지 상담하는 수익을 비교해서 최댓값을 갱신시켜줬다.

 

소스코드

#include <iostream>
#include <vector>

using namespace std;

int n, t[16], p[16], dp[16];

int main(){
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> t[i] >> p[i];
	}
	int res = 0;

	for (int i = 0; i < n; i++) {
		dp[i] = max(res, dp[i]);
		//퇴사전까지 상담 마칠수있으면 지금 날짜에 일한거랑 비교
		if (t[i] + i <= n) dp[t[i] + i] = max(dp[t[i] + i], p[i] + dp[i]);
		res = max(res, dp[i]);
	}
	cout << res;
}

+) 추가

 

---

DFS방식

 

DP를 풀면서도 생각을 했지만, 어차피 완전탐색으로 전체를 돌거기때문에 DFS로도 풀리지 않을까 라는 생각이 들었다.

 

#include <iostream>
#include <vector>

using namespace std;

int n, t[16], p[16], dp[16], res;

void dfs(int day, int sum) {
	if (day > n) return;
	res = max(res, sum);
	for (int i = day; i < n; i++) {
		dfs(i + t[i], sum + p[i]);
	}
	
}

int main(){
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> t[i] >> p[i];
	}
	dfs(0, 0);
	cout << res;
}

 

나한테는 DFS가 조금 더 직관적이고, 로직이 간결하다고 느껴졌다.