백준 14501 : 퇴사 (실버3) - 완탐, DP(재귀), DP(반복)

문제

---

백준 14501 : 퇴사 (실버3) - 완탐, DP(재귀), DP(반복)

문제 해석

---

최적화 문제.

 

제한된 조건으로 상담을 선택해 최대 이익을 출력합니다.

- i 일의 상담을 선택하면, i + t [i] 일부터 다시 상담을 시작할 수 있다

 

 

통찰

---

1. 완전 탐색(brute force) + backtracking

현재 날짜부터 가능한 모든 경우의 수를 탐색합니다.

더 이상 선택할 수 없을 때까지 재귀 호출합니다.

 

dp[i] = 시작일이 i 일 때 최대 이익
dp[i] = max (p[j] + dp[i+t[j]]), (i<=j<n)
정답 = dp[0]

 

2. DP 재귀

1에서 사용한 재귀 함수를 조금 변형하여 dp로 사용합니다. (참조적 투명성이 보장되도록 재귀 함수 구성)

 

 

3. DP 반복

2에서 사용한 DP의 cache가 채워지는 순서를 보고 반복문을 만듭니다. 

 

시간 복잡도

---

1. 완전 탐색

2^N = 2^15 = 32*1000 < 20억

 

2. DP

N^2 = 15^2 = 225 < 20억

 

풀이

---

1. brute force + backtracking

/**
 * @template file author kadrick (kbk2581553@gmail.com)
 *
 * author:amkorousagi (hasmi5452@gmail.com)
 */
#include <bits/stdc++.h>
using namespace std;
#define fastio                                                                 \
  ios::sync_with_stdio(false);                                                 \
  cin.tie(0);
#define endl '\n'

int mmax;
vector<int> t;
vector<int> p;
int n;
int sum;
void s(int start) {
	if (start == n) {
		mmax = max(mmax, sum);
	}

	for (int i = start; i < n; i++) {
		if (i + t[i] - 1 < n) {
			sum += p[i];
			s(i + t[i]);
			sum -= p[i];
		}
		else {
			mmax = max(mmax, sum);
		}
	}

}

int main(void) {
	fastio;
	
	cin >> n;

	t.assign(n,0);
	p.assign(n,0);

	for (int i = 0; i < n; i++) {
		cin >> t[i] >> p[i];
	}
	s(0);
	cout << mmax;
	



	return 0;
}

 

 

2. DP 재귀

/**
 * @template file author kadrick (kbk2581553@gmail.com)
 *
 * author:amkorousagi (hasmi5452@gmail.com)
 */
#include <bits/stdc++.h>
using namespace std;
#define fastio                                                                 \
  ios::sync_with_stdio(false);                                                 \
  cin.tie(0);
#define endl '\n'

int mmax;
vector<int> t;
vector<int> p;
vector<int> dp;
int n;
int s(int start) {
	if (dp[start] != -1) {
		return dp[start];
	}


	int mmax = 0;
	for (int i = start; i < n; i++) {
		if (i + t[i] <= n) {
			mmax = max(mmax, p[i] + s(i + t[i]));
		}
	}
	dp[start] = mmax;
	return mmax;

}

int main(void) {
	fastio;
	
	cin >> n;

	t.assign(n,0);
	p.assign(n,0);
	dp.assign(n + 1,-1);
	dp[n] = 0;
	for (int i = 0; i < n; i++) {
		cin >> t[i] >> p[i];
	}

	cout << s(0);
	



	return 0;
}

 

 

3. DP 반복

/**
 * @template file author kadrick (kbk2581553@gmail.com)
 *
 * author:amkorousagi (hasmi5452@gmail.com)
 */
#include <bits/stdc++.h>
using namespace std;
#define fastio                                                                 \
  ios::sync_with_stdio(false);                                                 \
  cin.tie(0);
#define endl '\n'

vector<int> t;
vector<int> p;
vector<int> dp;
int n;
int main(void) {
	fastio;
	
	cin >> n;

	t.assign(n,0);
	p.assign(n,0);
	dp.assign(n + 1,0);
	for (int i = 0; i < n; i++) {
		cin >> t[i] >> p[i];
	}

	int mmax;
	for (int i = n-1; i >= 0; i--) {
		mmax = 0;
		for (int j = i; j < n; j++) {
			if(j + t[j]<=n)
				mmax = max(mmax, p[j] + dp[j + t[j]]);
		}
		dp[i] = mmax;
	}


	cout << dp[0];
	



	return 0;
}