[삼성 14501] 퇴사

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

문제 설명

상담원으로 일하다 퇴사하는 백준이는 남은 n일간 가장 돈을 많이 벌 수 있는 스케줄을 짜야한다.
1. 이 회사의 상담은 하루에 하나씩 개최된다.
2. 상담은 시작일, 소요 날 수, 보수로 구성된다.
3. 백준이는 하루에 하나의 상담에만 참여할 수 있으며, 계약일 이후까지 이어지는 상담에는 참여할 수 없다.
4. 1<=n<=15

아이디어

n이 15라서 nC1~nCn의 모든 일거리 조합을 훑으면서 존재할 수 있는 스케줄인지 확인하고 최대 보수를 구할 수 있다.

구현 편의

next_permutation()을 이용하여 조합의 경우를 구한다.(경우의 수 말고)

코드

//퇴사
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

struct job {
	int s,e, p;//시작하는 날, 마지막날, 보수
	job(int ss, int ee, int pp) {
		s = ss;
		e = ee;
		p = pp;
	}

};

int n;
bool insertable(int schedule[15], job j) {
	if (j.e >= n) {
		return false;
	}
	for (int i = j.s; i <= j.e; i++) {
		if (schedule[i] == 1) {
			return false;
		}
	}
	return true;
}
void insert(int schedule[15], job j) {
	for (int i = j.s; i <= j.e; i++) {
		schedule[i] = 1;
	}
}


int main() {
	//next_permutation()
	cin >> n;
	vector<job> v;
	int t, p;
	for (int i = 0; i < n; i++) {
		cin >> t >> p;
		job j = job(i, t + i-1, p);
		v.push_back(j);
	}
	int* jevi = new int[n];
	int* jevi_c = new int[n];
	for (int i = 0; i < n; i++) {
		jevi[i] = 0;
	}
	int max_pay = 0;
	for (int i = n-1; i >=0 ; i--) {// 표를 하나씩 더 풀면서 검사해 갈거임
		//조합이니까 사실 n/2+1개까지만 표 풀어도 되는줄알았는데!!! 아님 1만 표로 취급하기 때문!
		jevi[i] = 1;
		copy(jevi, jevi+n, jevi_c);
		//cout << "nCt: " << n << " C " << i + 1 << endl;
		do {//jevi_c를 순열 돌림, 일 조합 하나씩 생성됨
			int schedule[15] = { 0 };
			bool valid = true;
			int cur_pay = 0;

			for (int i = 0; i < n; i++) {
				if (jevi_c[i] == 1) {//이 일이 들어갈 수 있을지 검사
					if (insertable(schedule, v[i])) {
						insert(schedule, v[i]);
						cur_pay += v[i].p;
					}
					else {
						valid = false;
						break;
					}
				}
			}
			if (valid&&cur_pay>max_pay) {
				max_pay = cur_pay;
			}
		} while (next_permutation(jevi_c,jevi_c+n));
		
	}
	cout << max_pay << endl;
}