[백준] 14501번 : 퇴사 & 15486번 : 퇴사2

🔗 문제 링크

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

---

✍️ 문제 풀이

해당 두 문제는 같은 다이나믹 프로그래밍 문제로, 첫 날부터 마지막 날까지 확인하면서 해당 날까지 일했을 때 얼마의 금액을 받을 수 있는지 저장해가면서 풀게 된다. 두 문제는 내용은 같지만 '퇴사 2' 문제에 주어지는 데이터의 크기가 훨씬 크기 때문에 제한 시간 내에 통과하기 위해서 풀이 방식을 개선했다. 두 문제 모두 Bottom-Up 방식으로 풀이했다.

[퇴사 1]

1) 전체 날짜의 길이와 상담들의 정보(기간, 금액)를 입력받아 n과 consultings에 저장한다. dp는 전부 0으로 초기화한다.

2) dp 배열을 첫 날부터 마지막 날까지 갱신한다.

• dp[i]에 저장되는 값 : i - 1일까지 일했을 때 받는 최대 금액
  • 일을 끝내야 금액을 받기 때문에 dp[n]에는 n일에 진행되는 상담은 포함하면 X
    ex. dp[4] = 1 ~ 3일에 일했을 때 받는 최대 금액 = 10
• 위 내용에 따라 현재 날짜의 각각의 이전 날짜들에 대해
  • 만약 현재 날짜 >= 이전 날짜 + 이전 날짜 상담에 걸리는 기간이라면 아래 점화식 반복
  • i : 현재 날짜 / j : 이전 날짜(범위 : 1 ~ i-1) / k : 이전 날짜 상담의 금액
  • dp[i] = max(dp[i], dp[j] + k)

3) dp[n + 1]을 출력한다. (dp[n + 1] == n일까지 일했을 때 받는 최대 금액)

[퇴사 2]

1) 전체 날짜의 길이와 상담들의 정보(기간, 금액)를 입력받아 n과 consultings에 저장한다. dp는 전부 0으로 초기화한다.

2) dp 배열을 첫 날부터 마지막 날까지 갱신한다.

• 현재 날짜를 먼저 갱신한다. 이전 날짜까지 최대 금액과 현재 날짜까지의 최대 금액을 비교해
  더 큰 금액을 현재 날짜의 최대 금액으로 갱신한다.
  • 현재 날짜 : i
  • 점화식 : dp[i] = max(dp[i], dp[i - 1])
• 현재 날짜에 잡힌 상담이 끝나는 날짜를 갱신한다. 해당 날짜까지의 최대 금액과 현재 날짜까지 금액 + 현재 날짜 상담 금액을 비교해 더 큰 금액을 해당 날짜의 최대 금액으로 갱신한다.
  • 현재 날짜 : i / 현재 날짜 상담 기간 : t / 현재 날짜 상담 금액 : p
  • 점화식 : dp[i + t] = max(dp[i + t], dp[i] + p)

3) dp[n + 1]을 출력한다.

✔️ 퇴사 2 동작 과정

1) DP를 전부 0으로 초기화 한다.

2) i = 1부터 n + 1까지 dp[i]를 갱신한다. 가장 처음으로 i = 1일 때

• dp[1] = max(dp[0], dp[1]) -> dp[1] = 0

• dp[1 + 3] = max(dp[1 + 3], dp[1] + 10) -> dp[4] = 10

  

3) i = 2일 때

• dp[2] = max(dp[1], dp[2]) -> dp[2] = 0
• dp[2 + 5] = max(dp[2 + 5], dp[2] + 20) -> dp[7] = 20

4) i = 3일 때

• dp[3] = max(dp[2], dp[3]) -> dp[3] = 0
• dp[3 + 1] = max(dp[3 + 1], dp[3] + 10) -> dp[4] = 10

5) i = 4일 때

• dp[4] = max(dp[3], dp[4]) -> dp[4] = 10
• dp[4 + 1] = max(dp[4 + 1], dp[4] + 20) -> dp[5] = 30

6) i = 5일 때

• dp[5] = max(dp[4], dp[5]) -> dp[5] = 30
• dp[5 + 2] = max(dp[5 + 2], dp[5] + 15) -> dp[7] = 45

7) i = 6일 때

• dp[6] = max(dp[5], dp[6]) -> dp[6] = 30
• dp[6 + 4] => dp[8]을 넘어가므로 의미 X

8) i = 7일 때

• dp[7] = max(dp[6], dp[7]) -> dp[7] = 45
• dp[7 + 2] => dp[8]을 넘어가므로 의미 X

8) i = 8일 때

• dp[8] = max(dp[7], dp[8]) -> dp[8] = 45
• dp[8 + 2] => dp[8]을 넘어가므로 의미 X

---

🖥️ 풀이 코드

[퇴사 1]

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;
typedef pair<int, int> pii;
int dp[16];
vector<pii> consultings;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int n;
	cin >> n;

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

	for (int i = 1; i <= n + 1; i++)
	{
		for (int j = 1; j < i; j++)
		{
			if (i >= j + consultings[j].first)
			{
				dp[i] = max(dp[i], dp[j] + consultings[j].second);
			}
		}
	}

	cout << dp[n + 1];
}

[퇴사 2]

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;
typedef pair<int, int> pii;
int dp[1500051];
pii consultings[1500051];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		int a, b;
		cin >> a >> b;
		consultings[i] = pii(a, b);
	}

	for (int i = 1; i <= n + 1; i++)
	{
		dp[i] = max(dp[i], dp[i - 1]);
		dp[i + consultings[i].first] = max(dp[i + consultings[i].first], dp[i] + consultings[i].second);
	}

	cout << dp[n + 1];
}