글 읽기 - 문제 풀이법에 대한 질문

blou888 1년 전 0

해당 문제가 dp라고 하는데,

저는 우선순위 큐로 해결 할 수 없는지 궁금합니다.

코드 돌아가는 방식은

pq의 top을 참조하고, pop,

pq가 비었다면, 그게 최댓값이므로, 출력을 해 주고,

아니라면, pq.top()이랑 같은지 비교해서 같다면 pq를 뽑아주고, 1증가시켜 다시 push 해 주었습니다.

하지만 AC를 받지 못했는데, 제가 생각하지 못한 반례가 있는지,

아니면 코드에 어느 부분이 틀렸는지 궁금합니다.

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

priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;

	while (N--) {
		int value;
		cin >> value;
		pq.push(value);
	}

	int value;
	while (!pq.empty()) {
		value = pq.top();
		pq.pop();
		if (pq.empty()) {
			cout << value << "\n";
			return 0;
		}
		if (pq.top() == value) {
			value++;
			pq.pop();
			pq.push(value);
		}
	}
}

blou888 1년 전 0

문제이해를 잘 못 했습니다!

2 1 2

같은 경우 2가 답이 되어야 하네요

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

문제

문제

출처

ICPC

문제 풀이법에 대한 질문

blou888 1년 전 0

blou888 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말