백준 17612번 문제를 풀다가 생긴 의문점입니다. (https://www.acmicpc.net/problem/17612)
다음 두 개의 코드의 차이가 무엇인가요? 첫 번째 코드는 잘 실행이 되지만, 두 번째 코드는 오답이 나옵니다.
이유가 무엇인지 잘 모르겠어서 질문글 올립니다.
--------------------------------------------------------
1
while(Cnt){
if(Top<=N){
auto[Ord,Id,Tm,Cnt1]=c[Top++];
PQ.push({Ord,Id,Tm+T,counter.back()});
counter.pop_back();
}
Cnt--;
}
--------------------------------------------------------
2
while(Cnt--){
if(Top<=N){
auto[Ord,Id,Tm,Cnt1]=c[Top++];
PQ.push({Ord,Id,Tm+T,counter.back()});
counter.pop_back();
}
}
아래는 전체 코드입니다.
--------------------------------------------------------
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
typedef long long int ll;
ll N,K,T,Top=1,Cnt;
ll sum;
vector <ll> v, counter;
struct customer{
ll ord;
ll id;
ll Time;
ll cnt;
bool operator<(const customer &r)const{
if(Time!=r.Time)return Time<r.Time;
return cnt>r.cnt;
}
bool operator>(const customer &r)const{
if(Time!=r.Time)return Time>r.Time;
return cnt<r.cnt;
}
};
customer c[100005],a;
priority_queue <customer,vector<customer>,greater<customer>> PQ; //min heap
int main()
{
scanf("%lld%lld",&N,&K);
for(int i=1;i<=N;i++){
c[i].ord=i;
scanf("%lld %lld",&c[i].id,&c[i].Time);
if(i<=K){
c[i].cnt=i;
PQ.push(c[i]);
Top++;
}
}
if(K>N){
Top=1;
while(!PQ.empty()){
sum+=PQ.top().id*Top;
Top++;
PQ.pop();
}
printf("%lld",sum);
return 0;
}
while(!PQ.empty()){
a=PQ.top();
T=a.Time;
while(!PQ.empty()&&PQ.top().Time==T){
auto[Ord,Id,Tm,Cnt1]=PQ.top();
v.push_back(Id);
PQ.pop();
Cnt++;
counter.push_back(Cnt1);
}
while(Cnt){
if(Top<=N){
auto[Ord,Id,Tm,Cnt1]=c[Top++];
PQ.push({Ord,Id,Tm+T,counter.back()});
counter.pop_back();
}
Cnt--;
}
}
for(int i=0;i<N;i++)
sum+=v[i]*(i+1);
printf("%lld",sum);
return 0;
}
2번 while앞에 if (Cnt)를 붙여봅시다
Cnt가 0인 시점에서 이상해지는 곳이 있을거 같고
아아... 변수를 그대로 불린으로 쓰는건 위험한 거군요! 감사합니다
그런건 아니고,, 조건식안에 증감연산자를 때려박으면 식을 평가할 때마다 묻지도 따지지도 않고 증감을 시킵니다 그냥 증감연산자를 식에 쓸 때 주의해야함