[백준] 26126 - 맛집 가이드 (c++)

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

 

문제 요약

평론가 두 명이 N개의 음식점에 각각 순위를 매긴다. 음식점을 등급으로 나눌 건데 각 등급의 음식점은 더 낮은 등급의 음식점 보다 더 높은 순위를 가져야 한다. 예를 들어 2등급에 {3,4}이 있으면 1등급에 {4,1}은 올 수 없고 {2,3}은 올 수 있다. 등급별 최소 음식점 개수가 K일 때 등급의 최대 개수를 구해라.

 

{a,b} := 1평론가에게 a의 평가를 받고 2평론가에게 b의 평가를 받은 음식점

 

풀이 (N)

• 그리디

등급이 몇개던 등급의 순서는 변하지 않기 때문에 K를 신경 쓰지 않고 최대한 세분화 한 뒤에 K보다 크게 합쳐주면 된다. 등급마다 각 순위가 한 번씩 등장한다는 성질을 이용하여 등급을 나눌 수 있다. 방법은 다음과 같다.

 

음식점마다 각 평론가의 순위를 입력받는다. 1번 평론가의 순위순으로 정렬해 순회하며 2번 평론가 순위의 최댓값을 갱신하면 i==mx일 때(각 순위가 한번씩 등장했을 때) 마다 등급을 나눌 수 있다. 마지막으로 등급을 나눴던 인덱스를 저장하고  i-lst>=k일 때마다 카운트해준다.

#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
    
    int n,k;cin >>n>>k;
    vector<array<int,2>> v(n);
    for(int i=1,a;i<=n;i++) cin>>a,v[a-1][0]=i;
    for(int i=1,a;i<=n;i++) cin>>a,v[a-1][1]=i;

    sort(v.begin(),v.end());
    int mx=0,i=1,lst=0,cnt=0;
    for(auto [a,b]:v) {
        mx=max(mx,b);
        if(i==mx&&i-lst>=k)
            cnt++,lst=i;
        i++;
    }   
    cout << cnt;
}