글 읽기 - 그리디 문제, 반례가 있을까요? 주석 상세히 달았습니다

kth990303 3년 전 0

우선 일이 끝나는 시각이 늦은 순대로 정렬을 했습니다.

이후, 일마다 가장 늦게 시작할 수 있는 시간들을 뽑고 그 중에서 가장 빠른 값을 뽑아냈습니다.

그리고, 모든 일을 하는데 걸리는 시간을 가장 늦게 끝내야되는 시각에서 빼서 위에서 뽑아낸 값이랑 더 빠른 시간을 답으로 했는데요 (이렇게 쓰니까 넘 어렵게 설명된 것 같네요.. 주석이랑 코드로 최대한 쉽게 풀어보았습니다)

이 코드의 논리가 어떤 점이 틀렸는지 잘 찾지 못하겠습니다. 일이 한 개일 때, 정렬이 뒤죽박죽일 때, 끝나는 시각이 같고 시간이 짬뽕일 때 등등의 테스트케이스를 만들어보았는데, 틀린 부분을 찾기가 쉽지 않네요.

고수분들 도와주십시오 ㅠㅠ

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int INF = 1000000007;
const int MAX = 1001;
int N;
vector<pair<int, int>> v;	// Ti, Si
// 정렬하는 방법: Si 오름차순, 같으면 Ti 오름차순
bool cmp(pair<int, int> p1, pair<int, int> p2) {
	if (p1.second == p2.second)
		return p1.first < p2.first;
	return p1.second < p2.second;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	for (int i = 0; i < N; i++) {
		int time, end;
		cin >> time >> end;
		v.push_back({ time, end });
	}
	sort(v.begin(), v.end(), cmp);
	int sum = 0, ans = INF;	// sum: 걸린 시간 합, ans: 답
	bool flag = true;	// false일 경우 불가능한 경우
	for (int i = 0; i < v.size(); i++) {
		sum += v[i].first;
		// 끝내야하는 시각보다 일의 합이 더 걸리면 불가능한 경우
		if (sum > v[i].second) {
			cout << -1 << "\n";
			return 0;
		}
		// 각 일마다 언제부터는 일을 해야된다
		ans = min(ans, v[i].second - v[i].first);
	}
	// 전체 걸리는 일의 시간 합 기준으로 언제부터 해야 하는지 보고
	// 더 빨리 해야되면 답 갱신
	ans = min(ans, v[v.size() - 1].second - sum);
	cout << ans << "\n";
	return 0;
}

kth990303 3년 전 7

자문자답하게 됐네요. 다른 방법으로 해서 맞춘 후, 맞춘 제 코드와 틀린 제 코드를 비교하면서 반례를 찾았습니다.

틀린 코드는 아래와 같은 경우 답이 1로 떠서 최소값이 제대로 갱신이 안됐었습니다.

각자의 일에서만 빼버리니까 이런 현상이 발생하네요

TC #4
4
3 4
1 4
5 17
2 20
ans: 0

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

그리디 문제, 반례가 있을까요? 주석 상세히 달았습니다

kth990303 3년 전 0

kth990303 3년 전 7

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말