백준 14222 배열과 연산 C++

해설

1부터 n까지 빈자리 모두 채워넣기

 

1부터 빈자리 찾아넣는다고 해서 그리디라고는 한다는거같은데 그리디의 개념은 조금 약한거 같다.

간단하게 풀기 가능

답

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n,k;
    cin>>n>>k;
    vector<int> v(n);
    for(int i=0;i<n;++i){
        cin>>v[i];
    }
    sort(v.begin(),v.end());
    vector<bool> visited(n,false);
    for(int i=0;i<n;++i){
        int val=v[i];
        if(visited[val]){
            for(int j=val;j<=n;j+=k){
                if(!visited[j]){
                    visited[j]=true;
                    break;
                }
            }
        }
        else{
            visited[val]=true;
        }
    }
    bool state=true;
    for(int i=1;i<=n;++i){
        if(!visited[i]){
            state=false;
            break;
        }
    }
    if(state) cout<<1;
    else cout<<0;
}