BOJ 2802 - 크레용

문제 링크 : https://www.acmicpc.net/problem/2802

문제 풀이

K개를 골랐을 때 최솟값을 구하는 문제...

문제를 딱 보면 최솟값을 구하는것이 아니라 특정 x값 이내가 되도록 k개를 고를 수 있는지에 대한 결정 문제로 변화시켜야 된다는 감을 잡을 수 있다. 즉, 파라메트릭 서치를 사용하면 될 것이라는 것이다. 

파라매트릭 서치를 사용한다고 치자. 어떤 m*m*m 범위가 존재하여 그 안에 k개가 있는 그러한 범위가 있는지를 빠르게 판별해야 한다. 위치가 바뀌지 않으니까, prefix sum을 이용하면 된다. 3차원 이기 때문에 포함과 배제의 원리와 prefix sum을 잘 이용하면 m*m*m 큐브 범위내의 수를 셀 수 있다.

구현이 살짝 까다롭다. 1차이 관리가 살짝 까다로우며 입력 범위가 0~255이기 때문에 prefix를 구할 때 고려를 해주어야 한다. 구현에서 실수할 여지는 좀 있지만, 문제 자체는 그렇게 어렵지 않은 문제.

코드

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> piii;
#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back
#define all(v) v.begin(), v.end()
 
ll arr[258][258][258];
ll pre[258][258][258];
ll sa,sb,sc,sk;
 
ll cal(ll a,ll b,ll c,ll k){
    return pre[a][b][c]-pre[a-k][b][c]-pre[a][b-k][c]-pre[a][b][c-k]
    +pre[a-k][b-k][c]+pre[a-k][b][c-k]+pre[a][b-k][c-k]-pre[a-k][b-k][c-k];
}
 
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    ll i,j,k,l,m,n,a,b,c;
    cin>>n>>m;
 
    for(i=1;i<=n;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        
        a++;
        b++;
        c++;
        arr[a][b][c]++;
    }
 
    for(i=1;i<=256;i++)
        for(j=1;j<=256;j++)
            for(k=1;k<=256;k++)
                pre[i][j][k]=arr[i][j][k]-cal(i,j,k,1);
            
 
    ll mid=0;
    ll lo=0,hi=257;
    while(lo<hi){
        ll chk=0;
        mid=(lo+hi)/2;
        for(i=mid+1;i<=256;i++)
            for(j=mid+1;j<=256;j++)
                for(k=mid+1;k<=256;k++)
                    if(cal(i,j,k,mid+1)>=m){
                        sa=i;
                        sb=j;
                        sc=k;
                        chk=1;
                        break;
                    }
                
        if(chk) hi=mid;
        else lo=mid+1;
    }
            
 
    mid=lo;
 
    for(i=mid+1;i<=256;i++)
        for(j=mid+1;j<=256;j++)
            for(k=mid+1;k<=256;k++)
                if(cal(i,j,k,mid+1)>=m){
                    sa=i;
                    sb=j;
                    sc=k;
                    break;
                }
                
        
    cout<<mid<<'\n';
    for(i=sa-mid;i<=sa;i++)
        for(j=sb-mid;j<=sb;j++)
            for(k=sc-mid;k<=sc;k++)
                while(m&&arr[i][j][k]){
                    m--;
                    arr[i][j][k]--;
                    cout<<i-1<<' '<<j-1<<' '<<k-1<<'\n';
                }
            
}