-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
구조체를 사용해 우선순위 큐를 사용하던중 이 코드가 왜 틀리는 건지 모르겠습니다.
21.08.23 04:17 작성 조회수 332
0
안녕하세요! 좋은 강의 찍어주셔서 감사합니다.!
구현체를 사용하여, 우선순위 큐를 구현해 문제를 풀었는데, 틀렸다고 떠서요.
동일 코드를 pair를 사용해 우선순위 큐 구현하여 코드를 올리면 맞았다고 뜹니다. 혹시 제가 잘못 사용했거나, 놓친 부분이 있을까요?
(문제 링크입니다:
https://www.acmicpc.net/problem/13549)
//정답 코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int vis[200001];
int main(){
cin.tie(0);
cout.tie(0);
std::ios::sync_with_stdio(false);
int n,k;
cin>>n>>k;
priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> >> pq;
pq.push({0,n});
vis[n]=1;
int res=987654321;
while (!pq.empty()) {
int move=pq.top().second;
int cnt=pq.top().first;
pq.pop();
if(move==k){
res=cnt;
break;
}
if(move*2<=200000&&vis[move*2]==0){
pq.push({cnt,move*2});
vis[move*2]=1;
}
if(move-1>=0&&vis[move-1]==0){
pq.push({cnt+1,move-1});
vis[move-1]=1;
}
//한칸 뒤 이동
if(move+1<=200000&&vis[move+1]==0){
pq.push({cnt+1,move+1});
vis[move+1]=1;
}
}
cout<<res<<"\n";
return 0;
}
//틀린코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
int vis[200001];
struct qu{
int m,val;
qu(int a,int b){
m=a;
val=b;
}
bool operator<(const qu & b)const{
return val>b.val;
}
};
int main(){
cin.tie(0);
cout.tie(0);
std::ios::sync_with_stdio(false);
int n,k;
cin>>n>>k;
priority_queue<qu>pq;
pq.push(qu{n,0});
vis[n]=1;
int res=987654321;
while (!pq.empty()) {
int move=pq.top().m;
int cnt=pq.top().val;
pq.pop();
if(move==k){
res=min(cnt,res);
break;
}
if(move*2<=200000&&vis[move*2]==0){
pq.push(qu(move*2,cnt));
vis[move*2]=1;
}
if(move-1>=0&&vis[move-1]==0){
pq.push(qu(move-1,cnt+1));
vis[move-1]=1;
}
//한칸 뒤 이동
if(move+1<=200000&&vis[move+1]==0){
pq.push(qu(move+1,cnt+1));
vis[move+1]=1;
}
}
cout<<res<<"\n";
return 0;
}
it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
75. 최대 수입 스케쥴(priority queue greedy: 구조체와 Vector를 이용한 정렬)
강의실 바로가기
답변을 작성해보세요.
1
김태원
지식공유자2021.08.24
안녕하세요^^
구조체 정렬기둔 함수를 아래와 같이 바꾸시면 될겁니다.
bool operator<(const qu & b)const{
if(val==b.val) return m>b.m;
return val>b.val;
}
답변 1