글 읽기 - 반례를 찾아주십쇼.. 주석있어요

mc_progw12 3년 전 0

당연한 얘기겠지만 잡아먹히는 상어 수의 최댓값을 구한 다음에 N에서 그 값을 빼는 방식으로 답을 구했고,

나머지는 아래 코드의 주석에 있습니다

#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
#define pii pair<int,int>
#define INF 1000000002
#define setting ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;

#define MAX 51

struct P{
    ll x,y,z;
};

ll n,m,ans;
P a[MAX]; // 상어 스탯 저장
ll vi[MAX],b[MAX]; // vi는 방문체크, b[i]에는 누가 i번째 상어를 먹는지를 기록합니다
vector<ll> v[MAX]; // A가 B를 먹을 수 있으면 v[a].push_back(B)

ll dfs(ll x){
    if(vi[x]) return 0;
    vi[x]=1;
    for(ll i:v[x]){
        //A가 B를 먹으려고 하면 B가 A를 먹지 않아야하고, 나머지는 열혈강호2와 동일
        if(b[x]!=i && (!b[i] || dfs(b[i]))){
            b[i] = x;
            return 1;
        }
    }
    return 0;
}

int main()
{
    setting;
    cin >>n;
    for(ll i=1;i<=n;i++){
        ll x,y,z;
        cin >>a[i].x>>a[i].y>>a[i].z;
        for(ll j=1;j<i;j++){
            // a[i]의 스탯이 a[j]보다 모두 좋으면
            if(a[i].x>=a[j].x && a[i].y>=a[j].y && a[i].z>=a[j].z){
                v[i].push_back(j);
            }
            // 그 반대
            if(a[i].x<=a[j].x && a[i].y<=a[j].y && a[i].z<=a[j].z){
                v[j].push_back(i);
            }
        }
    }
    
    for(ll i=1;i<=n;i++){
        memset(vi,0,sizeof(vi));
        ans += dfs(i);
        memset(vi,0,sizeof(vi));
        ans += dfs(i);
    }
    cout << n-ans;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 찾아주십쇼.. 주석있어요

mc_progw12 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말