1-A-B 백준 14501번 퇴사 (+ 퇴사 2)

알고리즘 캠프에서 풀었던 다른 문제들:

알고리즘 캠프 인덱스

문제 링크:

14501번: 퇴사

15486번: 퇴사 2

선배님이 가르쳐주신 BF의 순서 해법과 선택 해법 모두 적용할 수 있다.
먼저 순서 해법을 적용하면 BF가 2^N번 호출된다.

모든 선택 개수에 대한 조합 C(N,0) + C(N,1) + ... + C(N,N-1) + C(N,N) = 2^N을 search한다.

일정이 중복되어 선택 불가한 선택지에 대한 불필요한 search가 발생한다.

/* 1. RE : S.size()는 size_type 타입이라서 (int)캐스트를 해야 원하는 사칙연산 값이 도출됨 -> 원하는 값이 나오지 않아 loop이 의도대로 돌지 않음 */
/* 2. 오답(정답에 마지막 P 원소가 더해진 값) : 마지막으로 선택된 일정과 퇴사의 중복 검사 누락 */
/* 3. RE : vector의 back() 메소드는 empty일 때 호출 불가 -> empty 검사 추가하기 */

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> S;
int T[15];
int P[15];
int a;
int b = 1;

void BF(int i) {
	cout << b++ << '\n';

	int Ps = 0;
	
	// 마지막 선택지를 제외한 선택지들에 대한 일정 중복 검사
	for (int s = 0; s < (int)S.size() - 1; ++s) {	/* 1 */
		if (S[s] + T[S[s]] > S[s + 1])
			goto choose;
	}
	// 마지막 선택지에 대한 퇴사 중복 검사
	if (!S.empty() && S.back() + T[S.back()] > N)	/* 2 */ /* 3 */
		goto choose;
	
	for (auto s : S)
		Ps += P[s];
	if (Ps > a)
		a = Ps;

	choose:
	for (; i < N; ++i) {
		S.push_back(i);
		BF(i + 1);
		S.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin >> N;

	for (int n = 0; n < N; ++n)
		cin >> T[n] >> P[n];

	BF(0);

	cout << a;

	return 0;
}

다음으로 선택해법을 적용하면 BF가 최대 2^N - (sum(min(Ti, N - i)) - N)번 호출된다.

각 선택지가 선택될 경우 탐색 인덱스 i가 Ti만큼(인덱스가 N을 초과할 수 없으므로 i + Ti가 N을 넘는다면 N - i만큼 증가한다.) 증가하기에 TI - 1(혹은 N - i - 1)만큼의 호출이 절감된다.

#include <iostream>

using namespace std;

int N;
int T[15], P[15];
int mPs;

void BF(int Ts, int Ps) {
	if (Ts > N) {
		return;
	}
	else if (Ts == N) {
		if (Ps > mPs)
			mPs = Ps;
		return;
	}

	// 상담하지 않은 경우
	BF(Ts + 1, Ps);

	// 상담한 경우
	BF(Ts + T[Ts], Ps + P[Ts]);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin >> N;

	for (int n = 0; n < N; ++n) {
		cin >> T[n] >> P[n];
	}

	BF(0, 0);

	cout << mPs;

	return 0;
}

선택지 idx를 기반으로 탐색 trimming이 발생할 경우 선택 해법을 적용하자.

(breadth wise trimming)

---

이 문제는 DP로도 해결할 수 있다.

먼저 Top-down 방식이다. Top-down 방식은 시간초과로 오답이다.

// DP - Top-down

/* 1. TC 모두 통과, 채점 결과 오답 : N을 초과하는 상담은 단순히 0을 반환하는 것이 아니라 선택 불가능하도록 페널티를 주어야! */

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int T[15], P[15];
int pen = -16000;

int DP(int n) {
	// base case
	if (n == N)
		return 0;

	if (n > N)
		return pen;

	return max(DP(n + 1), P[n] + DP(n + T[n]));
}

int main() {
	ios_base::sync_with_stdio(0);
	cin >> N;
	for (int n = 0; n < N; ++n) {
		cin >> T[n] >> P[n];
	}

	cout << DP(0);

	return 0;
}

다음은 Bottom-up 방식이다.

Top-down 방식과는 다르게 퇴사2 문제를 해결할 수 있다.

Top-down 방식은 재귀 비용과 base case에 대한 판단 비용이 모든 호출에서 발생한다. 퇴사와 중복되어 수행할 수 없는 상담에 대해 감지 직후 수행을 중단하는 Bottom-up과 달리 감지 후 반환 및 덧셈, max 연산에 대한 overhead가 있어 퇴사2 문제에 대해 시간 초과가 발생한다.

// DP - Bottom-up

/* 1. 오답(0) : A의 의미가 idx일부터의 최대 수익인데, A[0]이 아닌 A[n]을 출력해버림 */

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int T[15];
int P[15];
int A[20];

void DP() {
	for (int n = N - 1; n >= 0; --n) {
		if (n + T[n] > N)
			A[n] = A[n + 1];
		else
			A[n] = max(P[n] + A[n + T[n]], A[n + 1]);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin >> N;
	for (int n = 0; n < N; ++n) {
		cin >> T[n] >> P[n];
	}

	DP();

	cout << A[0];

	return 0;
}