글 읽기 - 정육점문제에서 제 코드의 문제를 알고싶습니다!!!

ehdwns1249 5년 전 0

제 코드내용은 이렇습니다.

1. 가격을 기준으로 정렬, 가격이 같다면 무게를 기준으로 정렬
2. 벡터의 첫 번째 무게가 기준을 충족한다면 cost 변수에 가격을 기록
3. 반복문으로 벡터의 두 번째부터 i-1번째와 i의 기존가격을 비교하며 가격이 같다면 i-1번째와 i번째의 가격과 무게를 모두 더함,
그렇지 않다면 무게만 더함
4. 만약 더해진 무게가 기준무게를 충족하면서, cost가 초기화 된 값 -1이거나 현재 가격이 cost보다 작다면 cost에 현재가격을 기록
5. cost 출력 (기준 무게를 충족하지 못하면 초기화 값 -1 출력)

문제가 뭘까요?..거의 채점시작도 못해보고 "틀렸습니다"가 뜨는데
극단적인 반례가 있을까요? 꽤 많이 넣어본 것 같은데 반례 찾기가 쉽지않네요 ㅠ

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(void) {
	int N, M;
	vector<pair<int, int> > v;
	vector<pair<int, int> >::iterator it;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back(make_pair(b, a)); // 가격을 기준으로 정렬하기 위해 b를먼저 넣어줌
	}
	sort(v.begin(), v.end()); //가격을 기준으로 정렬, 가격이 같다면 무게를 정렬

	int cost = -1;
	if (v.begin()->second >= M) {//처음 무게가 M을 넘는다면 가격 기록
		cost = v.begin()->first;
	}
	int x = v.begin()->first;//첫 가격 기록
	for (it = v.begin() + 1; it != v.end(); it++) {//두번째 목록부터 접근
		int p = it->first;//임시로 저장
		if (x== it->first) { // 이전의 가격과 현재 가격이 같다면
			it->first += (it-1)->first; //현재가격 +=이전가격,,,, -> 같은가격을 여러개 사는 경우를 처리
			it->second += (it - 1)->second;// 현재까지의 총무게량
			
		}
		else { //이전가격과 현재가격이 다르다면
			it->second += (it - 1)->second; //무게만 더해줌
		}
		if (it->second >= M && (cost==-1 || cost>it->first)) {//총무게가 M과 같거나 크면서 기록되어있는 cost가 더 크다면 cost 변경
			cost = it->first;
		}
		x = p;//이전가격기록
	}

	cout << cost << "\n";
}

piy0605 5년 전 1

네 혹시 광운대다니세요?

4 3

1 2

3 2

2 2

5 7

답 : 2

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

문제

문제

출처

ICPC

정육점문제에서 제 코드의 문제를 알고싶습니다!!!

ehdwns1249 5년 전 0

piy0605 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말