백준 14501번 퇴사 C++ 구현해보기

---

```

백준 14501번 퇴사 C++ 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  백준 14501번 풀이

---

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

14501번: 퇴사

 

 

 

백준 14501번 퇴사는

난이도 실버 등급의 문제로서

 

상담사로 영업을 하는 직원 B가 퇴사를 할 경우

퇴사 전 이익을 최대화하기 위한

 

업무 배정을 정하는 문제이다.

 

 

입력은

첫줄에 날짜의 개수 N이 주어지고

주어지는 날짜마다

업무가 완수되는데 걸리는 날짜

업무를 완수함으로 받는 보상이 주어진다.

 

예를 들어

3

1 3

1 1

1 1

이 입력으로 주어질 경우

 

첫째 날 받은 업무가 3의 보상을 주기 때문에 3을 더하고

다음날 받은 업무가 1의 보상

그다음 날 받은 업무가 1의 보상을 줘서

총 5의 보상을 받는다.

 

다시 예를 들어

5
5 10
1 1
1 1
1 1
2 11

가 주어질 경우

첫날 5일짜리 업무를 하고 10의 보상을 받는 게

2,3,4일에 1일씩 업무를 하고 3의 보상을 받는 것보다 이득이 크다.

마지막 날의 경우 업무일 수가 남은 날보다 크기 때문에 제외된다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

저의 경우 객체 인스턴스를 만들어서

 

각 날짜마다 필요한 업무 일수와 보상을 배열로 입력받고

	void setDailyWorkDistribution(const int32_t idx, const int32_t requiredDate, const int32_t givenReward)
	{
		daysArr[idx].requiredDate = requiredDate;
		daysArr[idx].givenReward = givenReward;
	}

 

DP와 Bruteforce를 사용해서

최대 보상을 계산했습니다.

	int32_t findMaxReward()
	{
		int32_t ret = findMaxReward(1);

		return ret;
	}

	int32_t findMaxReward(const int32_t curDate)
	{
		int32_t ret = 0;

		if (curDate <= numOfDaysLeft + 1)
		{
			int32_t tempVal1 = 0;
			int32_t tempVal2 = findMaxReward(curDate + 1);

			if ((curDate + daysArr[curDate].requiredDate) <= numOfDaysLeft + 1)
			{
				tempVal1 = daysArr[curDate].givenReward + findMaxReward(curDate + daysArr[curDate].requiredDate);
			}

			ret += std::max(tempVal1, tempVal2);
		}

		//std::cout << curDate << " " << daysArr[curDate].requiredDate << "\n";
		return ret;
	}

 

 

 

전체 코드는 다음과 같습니다

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <regex>

constexpr int32_t maxNumOfDaysLeft = 30;

class CTelecomJob
{
private:

	int32_t numOfDaysLeft;

	struct DailyWorkDistribution
	{
		// 상담을 완료하는데 걸리는 기간(날짜) Ti
		int32_t requiredDate;
		// 상담을 완료하는데 받는 금액() Pi
		int32_t givenReward;
	};

	std::array<DailyWorkDistribution, maxNumOfDaysLeft> daysArr;

public:
	CTelecomJob(int32_t size)
	{
		numOfDaysLeft = size;

		for (int32_t i = 0; i < maxNumOfDaysLeft; i++)
		{
			daysArr[i].givenReward = 0;
			daysArr[i].requiredDate = 1;
		}
	}
	~CTelecomJob()
	{

	}

	void setDailyWorkDistribution(const int32_t idx, const int32_t requiredDate, const int32_t givenReward)
	{
		daysArr[idx].requiredDate = requiredDate;
		daysArr[idx].givenReward = givenReward;
	}

	int32_t findMaxReward()
	{
		int32_t ret = findMaxReward(1);

		return ret;
	}

	int32_t findMaxReward(const int32_t curDate)
	{
		int32_t ret = 0;

		if (curDate <= numOfDaysLeft + 1)
		{
			int32_t tempVal1 = 0;
			int32_t tempVal2 = findMaxReward(curDate + 1);

			if ((curDate + daysArr[curDate].requiredDate) <= numOfDaysLeft + 1)
			{
				tempVal1 = daysArr[curDate].givenReward + findMaxReward(curDate + daysArr[curDate].requiredDate);
			}

			ret += std::max(tempVal1, tempVal2);
		}

		//std::cout << curDate << " " << daysArr[curDate].requiredDate << "\n";
		return ret;
	}

	void printDailyWorkDistribution()
	{
		for (int32_t i = 1; i <= numOfDaysLeft; i++)
		{
			std::cout << i << " " << daysArr[i].requiredDate << " " << daysArr[i].givenReward << "\n";
		}
	}

};


int main()
{
	// 입력 최적화
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	int32_t N;
	std::cin >> N;
	std::cin.ignore();

	std::string inputStr;

	CTelecomJob* cTelecomJob = new CTelecomJob(N);

	for (int32_t i = 1; i <= N; i++)
	{
		std::getline(std::cin, inputStr);
		std::stringstream ss(inputStr);
		int32_t requiredDate;
		int32_t givenReward;
		ss >> requiredDate;
		ss >> givenReward;
		cTelecomJob->setDailyWorkDistribution(i, requiredDate, givenReward);
	}
	//cTelecomJob->printDailyWorkDistribution();

	int32_t maxReward = cTelecomJob->findMaxReward();
	std::cout << maxReward;
}

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

참조 및 인용

C++ Primer

Introduction to Algorithms

---

https://codemasterkimc.tistory.com/35

C++ 이론을 배울수 있는 곳 정리

 

https://codemasterkimc.tistory.com/50

300년차 개발자의 좋은 코드 5계명 (Clean Code)

 

---