백준 14501 퇴사 c++ // dfs, dp, 트리하부호출 되는경우만 dfs실행

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

14501번: 퇴사

1. 의사코드

테이블을 그리는것을 좋은선택이다.

 

def dfs(n, sm): //dfs(인덱스, 현재돈)
    global ans
    # [1] 종료조건: 가능한 n을 종료에 관련된것으로 정의!
    if n>=N:
        ans = max(ans, sm)
        return

    # [2] 하부호출: 화살표 개수만큼 호출
    if n+T[n]<=N:   # 상담하는 경우(퇴사일전 완료 가능할 때만 상답)
        dfs(n+T[n], sm+P[n])
    dfs(n+1, sm)    # 상담 하지 않는 경우(항상 가능)

좌측하부호출은 n+T[n]이 N이하일때만 호출하도록 구현하자.

하부호출의 가능성을 따져야한다!!

 

2. dfs 기존코드

#include <bits/stdc++.h>

using namespace std;

int n,vis[16],ret;
vector<pair<int, int>> v1,v2;

void dfs(int day, int money) {

	if (day == n) {
		ret = max(ret, money);
		return;
	}
	if (day > n) return; //마지막 수업을 들을수 없는경우(막날수업이 2일이상 소요되는경우)

	dfs(day+v1[day].first, money + v1[day].second); //해당강의선택
	dfs(day+1, money); //미선택
}

int main() {
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		v1.push_back({ a,b });
	}

	dfs(0, 0);
	cout << ret;
	//sort(v1.begin(), v1.end(),cmp);

	/*for (auto p : v1) {
		if (vis[p.first]) continue;
		vis[p.first] = 1;
		v2.push_back({ p.first,p.second });
	}

	for (auto p : v2) {
		cout << p.first << " " << p.second<<"\n";
	}*/


	return 0;
}

 

3. dp 의사코드 (N=15가아니라, N이크다면 dp로 풀어야함)

1. dp는 테이블 정의후, 뒤부터접근 , 규칙찾기

 

dp = [0]*(N+1)
for n in range(N-1, -1, -1):    # 뒤에서 앞으로(완료기준)
    if n+T[n]<=N:               # 기간내 상담완료 가능
        dp[n]=max(dp[n+1], dp[n+T[n]]+P[n])
    else:
        dp[n]=dp[n+1]

print(dp[0])