글 읽기 - priority_queue 반례나 틀린 이유를 모르겠습니다

kth990303 3년 전 0

안녕하세요

이 문제를 bfs로 해결하려다가 질문게시판 글들을 보고

덱 또는 우선순위 큐로 해결해야겠다 싶어 덱으로 해결하였고,

이번엔 우선순위 큐로 해결해보려 하였습니다.

그런데 아래의 코드가 틀린 이유를 모르겠습니다. 질문게시판의 반례를 적용해보았을 때 제대로 나왔고, 예제의 5 17 또한 제대로 2가 나왔고, 그 외에

5 100000, 6 100000, 50000 100000, 1 65536 등을 넣어보았는데 제대로 나와 틀린 이유를 도무지 모르겠어서 질문글을 쓰게 됐습니다.

도움 부탁드립니다 ㅠㅠ

#include <iostream>
#include <queue>
#include <deque>
#include <vector>
#include <functional>
using namespace std;
bool d[100001];
int A[100001];
int n, k;
int main() {
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios_base::sync_with_stdio(false);

	priority_queue<pair<int, int>, vector<pair<int, int>>,greater<pair<int, int>>> q;
	cin >> n >> k;
	q.push({ n, 0 });
	d[n] = true;
	while (!q.empty()) {
		int a = q.top().first;
		int cnt = q.top().second;
		q.pop();
		if (a == k)
			break;
		if (a <= 50000 && !d[2 * a]) {
			d[2 * a] = true;
			A[a * 2] = A[a];
			q.push({ 2 * a, cnt  });
		}
		if (a + 1 <= 100000 && !d[a + 1]) {
			d[a + 1] = true;
			A[a + 1] = A[a] + 1;
			q.push({ a + 1, cnt + 1 });
		}
		if (a - 1 >= 0 && !d[a - 1]) {
			d[a - 1] = true;
			A[a - 1] = A[a] + 1;
			q.push({ a - 1, cnt + 1 });
		}

	}
	cout << A[k];
	return 0;
}

shg9411 3년 전 2

반례입니다.

input
3 11

output
3

answer
1
3(0) -> 6(0) -> 12(0)-> 11(1)

kth990303 3년 전 0

저 때 제가 너무 정신없었나 보네요 ㅠㅠ priority queue인데... 반례 감사합니다

adxx 3년 전 0

저는 이 반례를 보고 범위를 2*k까지 찾아 주어 AC를 받을 수 있었습니다

그러니까 주어진 k보다 조금 더 가서 다시 뒤로 오는 경우에도 최단거리가 존재 할 수 있다는 점을 알게해주는 반례입니다👍

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

문제

문제

출처

ICPC

priority_queue 반례나 틀린 이유를 모르겠습니다

kth990303 3년 전 0

shg9411 3년 전 2

kth990303 3년 전 0

adxx 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말