[ BOJ 백준 3430번 - 용이 산다 ] 해설 및 코드

https://www.acmicpc.net/problem/3430

목적

비가 내려 호수에 물이 넘치지 않도록 용이 호수 물을 먹는 순서를 구하자.

 

접근법

1. t[i]가 자연수일때, 즉 비가 내릴 때, 미리 우물을 비워야 한다. 탐욕적으로 비가 내리지 않는 날 중에서 가능한 가장 이른 날을 선택해야 한다. 왜냐하면 매 순간마다 선택할 수 있는 선택지를 최대한 많이 확보해야 하기 때문이다.

 

2. 선택할 수 있는 범위는, t[j]==t[i](j는 j<i인 수 중 최대값)일 때, j+1일째 부터이다. 

 

#include<iostream>
#include<set>
#include<algorithm>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
const int LEN = 1e6+1;
int n,m,ans[LEN],a[LEN];
 
bool go(){
    set<int> s;
    f(i,1,m){
        int t;cin>>t;
        if(t==0){
            s.insert(i);
            ans[i]=0;
        }
        else{
            set<int>::iterator it=s.upper_bound(a[t]);
            if(it==s.end()){
                while(m-->i)cin>>t;
                return false;
            }
            
            ans[*it]=t;
            a[t]=i;
            s.erase(it);
        }
    }
    return true;
}
 
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int z;cin>>z;
    while(z--){
        cin>>n>>m;
        f(i,1,m)a[i]=ans[i]=-1;
 
        if(go()){
            cout<<"YES\n";
            f(i,1,m)if(ans[i]!=-1)cout<<ans[i]<<' ';
            cout<<'\n';
        }else cout<<"NO\n";
    }
    return 0;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.