글 읽기 - [C++] 비드맨 반례 부탁드립니다.

jeong5728 3년 전 0

최대힙 사용해서 제일 큰 값, 그 다음으로 큰 값 2개씩 pop 하여 구슬의 개수를 줄여 나갔습니다.

이렇게 하면 문제 없겠다 싶었는데 50% 정도에서 틀렸습니다가 출력되네요..

틀린 점이나 반례 부탁드립니다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(){
	int N;
	scanf("%d", &N);

	int count;
	int bead[N] = {0};
	priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pq; // 구슬의 개수, 종류
	for(int i = 0; i < N; i++){
		scanf("%d", &count);
		bead[i] = count;
		pq.push(make_pair(count, i));
	}

	while(pq.size() > 1){
		auto one = pq.top();
		pq.pop();
		auto two = pq.top();
		pq.pop();

		bead[one.second] -= two.first;
		bead[two.second] -= two.first;

		if(one.first-two.first != 0){
			pq.push(make_pair(one.first-two.first, one.second));
		}
	}

	int sum = 0;
	for(int i = 0; i < N; i++){
		sum += bead[i];
	}
	printf("%d\n", sum);

	return 0;
}

pichulia 3년 전 2

반례입니다.

정답은 0입니다.

3
2 8 8

jeong5728 3년 전 0

주신 반례를 보고 문제를 여러번 다시 읽어보니 제가 룰을 잘못 이해하고 있었네요. 답변 감사합니다.

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

문제

문제

출처

ICPC

[C++] 비드맨 반례 부탁드립니다.

jeong5728 3년 전 0

pichulia 3년 전 2

jeong5728 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말