[학교 과제] 프리랜서 (c++)

문제

고급 주택을 청소해주는 프리랜서가 있다. 최대한의 이익을 얻기 위해서 청소 스캐쥴을 짜야한다.

입력으로는 N이 주어지는데 N개의 청소할 수 있는 곳이 나온다 

다음 N개의 줄에는 시작일, 마감일, 비용이 나오고 같은 비용일 때는 적은 일을 한 스캐줄이 선택 받는다.

주택을 옮기는데 비용이 들기 때문에 10만원이라는 지출이 발생한다.

일이 1일에서 3일까지 라면 3일 까지 일을 하는 것이기 때문에 3일에 일을 시작 할 순 없다.

해결 방법

dp 문제로 처음에는 일을 시작하는 날을 기준으로 cache의 인덱스를 정했지만 이러면 같은 날 시작하는 일이 2개 있을 경우 먼저 나온 일로 cache에 저장 되기 때문에 해결 할 수 없다.

그래서 일이 입력된 인덱스를 cache의 인덱스로 잡아 해결 하였다.

재귀 호출을 할 땐 일의 끝나는 날보다 더 늦게 일을 시작하는 일의 리스트를 저장해 두고 각각 리스트 원소를 마지막 일로 하는 경우로 설정후 또 재귀 호출을 반복하여 이중 최대 이익중 최소 일을 하는 케이스를 리턴하였다.

주택을 옮길 때마다 비용이 발생하므로 마지막 재귀호출 제외한 재귀호출에서 호출시 비용 -10을 해주었다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>

using namespace std;

int cost_cache[101];
int day_cache[101];
int N;

bool desc(vector<int>& a, vector<int>& b) {
	return a[0] > b[0];
}
//day 는 시작하는 날 0 index는 자기 자신의 정보
vector<int> f(vector<int>& b, vector<int>& e, vector<int>& c, int day, int index) {
	vector<int> ret(2);
	if (index != -1) {        
        if (cost_cache[index] != -1) {
            ret[0] = cost_cache[index];
            ret[1] = day_cache[index];
            return ret;
        }
    }
	vector<vector<int>> list1;
	for (int i = 0; i < N; i++) {
		if (day < b[i]) { // 시 작
			list1.push_back(f(b, e, c, e[i], i));
		}
	}
	// 마지막 주택 
	if (list1.empty()) {
        ret[0] = c[index];
        ret[1] = e[index] - b[index] + 1;
        return ret;
	}
	sort(list1.begin(), list1.end(), desc);
	int target = 0;
	int i = 1;
	if (list1.size() >= 2) {
		// 같은 최대이익이 여러개인 경우 최소 일 선택 
        while (list1[target][0] == list1[i][0]) {
            if (list1[target][1] > list1[i][1]) {
                target = i;
                i++;
            }
            else i++;
            if (target >= list1.size() || i >= list1.size()) break;
        }
	}
	ret = list1[target];
	if (index != -1) {
		// 비용 -10 
        ret[0] += c[index] - 10;
        ret[1] += e[index] - b[index] + 1;
	}
	if (index != -1) {
        if (cost_cache[index] < ret[0]) {
            cost_cache[index] = ret[0];
            day_cache[index] = ret[1];
        }
        else if (cost_cache[index] == ret[0])	{
            if (day_cache[index] > ret[1]) {
                cost_cache[index] = ret[0];
                day_cache[index] = ret[1];
            }
        }
	}
	return ret;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	memset(cost_cache, -1, sizeof(cost_cache));
	memset(day_cache, -1, sizeof(day_cache));
	

	cin >> N;
	vector<int> b(N), e(N), c(N);
	for (int i = 0; i < N; i++) {
		cin >> b[i] >> e[i] >> c[i];
	}
	vector<int> answer = f(b, e, c, 0, -1);
	cout << answer[0] << " " << answer[1];	
    return 0;
}