취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6136번 문제인 Milking Time이다.
문제는 아래 링크를 확인하자.

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

각 스케줄의 시작시간을 S, 끝나는 시간을 E라 할 때, 주어진 스케줄 [S,E]를 소화하면 [S,E+R] (R: 휴식시간)의 기간동안 다른 스케줄을 소화할 수 없고 efficiency만큼의 우유를 얻을 수 있다.

시간 흐름순으로 살펴보면서, 각 시간에 일하기 시작할 수 있는 상태이면서 가장 많은 우유를 얻은 양을 이용해 구하는 값을 dp로 구해나가면 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

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

int dp[2000001];
pair<pair<int, int>, int> interval[1000];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M, R; cin >> N >> M >> R;
	for (int m = 0; m < M; m++) {
		int x, y, e; cin >> x >> y >> e; y += R;
		interval[m] = make_pair(make_pair(x, y), e);
	}

	sort(interval, interval + M);

	int idx = 0, m = 0;
	while (m < M) {
		int S = interval[m].first.first, E = interval[m].first.second, eff = interval[m].second;
		while (idx < S) {
			dp[idx + 1] = max(dp[idx + 1], dp[idx]);
			idx++;
		}
		dp[E] = max(dp[E], dp[S] + eff);

		m++;
	}
	while (idx < 2000001) {
		dp[idx + 1] = max(dp[idx + 1], dp[idx]);
		idx++;
	}

	cout << dp[2000000];
}