백준 19621, 19622 회의실배정 2, 3

방학부터 시작해서 여러 가지 문제들을 풀었지만 내가 푼 문제 수에 비해 얻은 지식량이 너무 미흡하고, 제대로 공부를 하고 있는 느낌이 들지 않아서 오답노트 겸 글을 남긴다. 

 

첫 번째 문제는 최근에 올라온 문제인 회의실 배정 2, 3이다.

 

www.acmicpc.net/problem/19621

19621번: 회의실 배정 2

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> ar;
int res, n;

void dfs(int cnt, int sum) {
	if (cnt > n - 1) {
		res = max(res, sum);
		return;
	}
	dfs(cnt + 1, sum);
	dfs(cnt + 2, sum + ar[cnt]);
}

int main() {
	cin >> n;
	ar.resize(n);
	for (int i = 0; i < n; i++) cin >> ar[i] >> ar[i] >> ar[i];
	dfs(0, 0);

	cout << res << endl;

	return 0;
}

 

회의실 배정 2는 백트래킹으로 해결했다. 

 

• 임의의 회의 K(1≤ K ≤ N)는 회의 K − 1과 회의 K + 1과는 회의 시간이 겹치고 다른 회의들과는 회의 시간이 겹치지 않는다.

이 조건에서 어짜피 정렬 순으로 나오고, 이번 회의에 참여했다면 그 전이나 다음 회의는 못하기에

dfs(cnt+1, sum) //이번 회의를 건너뛴다면,
dfs(cnt+2, sum + ar[cnt]) //이번 회의에 참석한다면,

 

이런 식으로 코드를 작성했고 

처음엔 if (cnt==n-1) 으로 작성했는데 종료 조건을 찾지 못하고 무한 루프에 빠지기에 금방 알아챘다.

 

www.acmicpc.net/problem/19622

19622번: 회의실 배정 3

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;

#define X first
#define Y second

ll d[100001][2]; //n번째, 참여 1, 미참 0
vector<pair<pair<ll, ll>, ll>> ar;

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

	ll n;
	cin >> n;
	ar.resize(n + 1);
	for (int i = 1; i <= n; i++) cin >> ar[i].X.X >> ar[i].X.Y >> ar[i].Y;

	d[1][1] = ar[1].Y;
	d[2][1] = ar[2].Y; d[2][0] = ar[1].Y;
	for (int i = 3; i <= n; i++) {
		d[i][0] = max(d[i - 1][0], d[i - 1][1]);
		d[i][1] = d[i - 1][0] + ar[i].Y;
	}
	cout << max(d[n][0], d[n][1]) << endl;

	return 0;
}

 

이번엔

• 1 ≤ N ≤ 100,000

이 조건 때문에 백트래킹으론 해결할 수 없다.

 

d[i][0] 은 회의에 참여하지 않음

d[i][1] 은 회의에 참여함

 

으로 두고 점화식을 세웠다.

 

		d[i][0] = max(d[i - 1][0], d[i - 1][1]);
		d[i][1] = d[i - 1][0] + ar[i].Y;

 

이번 회의에 참여하지 않았다면, 전 회의에 참여한 것과, 참여하지 않은 것의 최댓값을 가져오고,

이번 회의에 참여했다면, 전 회의에는 참여하지 못하니 d[i-1][0] 에 현재 값을 더해준다.

 

이친 수 문제와 비슷한 것 같다.