글 읽기 - 2258 정육점 어디가 틀린건가요

cubalys 8년 전 0

먼저 가격 순으로 정렬한 후

낮은 가격부터 탐색하여

처음으로 현재 고기보다 싼고기 무게합 + 현재고기 무게 가 사고자 하는 무게를 넘어 갈 때 빠져나와 현재 고기의 값을 출력했습니다.

고기의 가격이 같은 경우가 있을 수 있으므로 그 부분은 따로 예외처리 해놓았습니다.

예제와 제가 만들어서 몇개 해봐도 잘 나오는 것 같은데

어디서 문제가 있는 걸까요

#include <iostream>
#include <algorithm>
using namespace std;
typedef struct meat{ 
    int weight;
    int money;
    bool operator()(meat p, meat q){
        if(p.money < q.money) return 1;
        else return 0;
    }
}MEAT;
MEAT gogi[100000];
int main(){
    int N, M, sum = 0, sum2 = 0, result = 0; //sum - 이번 고기를 샀을때 가지고 갈 수 있는 고기의 양 
    cin>>N>>M;
    for(int i=0; i<N; i++) 
		cin>>gogi[i].weight>>gogi[i].money; 
    sort(gogi, gogi+N, meat()); 
	for(int i=0; i<N; i++){
		if(i>0 && gogi[i].money == gogi[i-1].money){ // 전 고기와 가격이 같을 때
			sum2 += gogi[i-1].weight; 
			sum -= gogi[i-1].weight; 
			sum += gogi[i].weight; 
		}
		else {
			sum += sum2 + gogi[i].weight;
			sum2 = 0;
		}
		if(sum >= M) {
			result = gogi[i].money;
			break;
		}
		if(i == N-1){
			result = -1;
			break;
		}
    }
	cout<<result<<endl;
}

cubalys 8년 전 0

아 같은 가격 고기를 여러개 살수 있단 생각을 못했네요 ㅜㅜ 하나만 산다고 생각하고 풀었어요 ㅋㅋ 감사합니다

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

문제

문제

출처

ICPC

2258 정육점 어디가 틀린건가요

cubalys 8년 전 0

cubalys 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말