글 읽기 - 2258 정육점 문제 코드 문제점 or 반례

bellbro2 4년 전 0

코드 짜고 문제의 예제와 여러 테스트케이스를 테스트 해봤는데 도무지 안돼서 질문드립니다..

코드의 문제점이나 반례를 찾아주시면 정말 감사드리겠습니다..

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

bool compare(const pair<int, int>& a, const pair<int, int>& b) {
	if (a.first == b.first) {
		return a.second > b.second;
	}
	return a.first > b.first;
}

pair<int, int> meat[100002];
int main() {
	int N, M, min = 0, weight = 0, max = 0;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> meat[i].first >> meat[i].second; // first : 고기 무게, second : 고기 가격
	}
	sort(meat, meat + N, compare); // 고기의 무게가 큰 순으로 정렬하되, 고기의 무게가 같을 때는 고기의 가격이 큰 순으로 정렬

	for (int i = 0; i < N; i++) {
		if (meat[i].first <= M) {
			max = meat[i].first; // 고기의 무게가 M보다 작거나 같을 때 가장 큰 값
			break;
		}
	}

	for (int i = 0; i < N; i++) {
		if (meat[i].first > M) // 고기의 무게가 M보다 클 시 continue
			continue;
		weight += meat[i].first;
		if (max > meat[i].first) // 가장 큰 고기의 무게보다 작은 고기들은 continue
			continue;
		min += meat[i].second;
		//cout << meat[i].first << " " << meat[i].second << endl;
	}

	for (int i = 0; i < N; i++) {
		if (meat[0].first == meat[i+1].first) {
			if (weight - meat[i].first >= M) {
				weight -= meat[i].first;
				min -= meat[i].second;
			}
			else break;
		}
	}

	if (weight < M) {
		cout << -1 << endl; // 
	}
	else
		cout << min << endl;

	return 0;
}

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

문제

문제

출처

ICPC

2258 정육점 문제 코드 문제점 or 반례

bellbro2 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말