[CF 1136D] Nastya Is Buying Lunch

[CF 1136D] Nastya Is Buying Lunch - 1800

문제 설명 : 

n명이 줄을 서 있고 문제의 주인공은 줄의 맨 뒤(n번째 인덱스)에 서 있다. 그리고 m개의 정보가 들어오는데 각 정보는 두 정수 a,b로 이루어져있다. 이 의미는 줄의 앞사람이 a번 사람이고 뒷사람이 b번 사람이라면 a와 b가 서로 자리를 바꿀 수 있다는 의미이다. 이 정보들을 바탕으로 n번째 사람은 최대 몇 칸이나 앞으로 움직일 수 있는지 구하는 문제이다.

풀이 : 

이 문제에서 관심이 있는 것은 맨 뒷사람(편의상 last라고 두자)이 최대 몇 칸이나 앞으로 움직일 수 있는지를 구하는 문제이다. 따라서 정보들 중에서 내가 관심있게 보는 것은 ( ? , last )라는 정보가 중요하지만 동시에 ? 직전까지 움직일수 있느냐도 관건이다. 

초기에 사람 수 만큼의 set을 준비해놓고 정보(a,b)가 들어오면 set[a]에 원소 b를 insert한다. 그리고 줄(order배열)의 맨 뒤에서 두 번째(주인공을 앞 사람)부터 last와 자리를 바꿀 수 있는지 확인한다. 확인하는 방법으로는 우선 set[a]에 last라는 원소가 있는지 확인해본다. 만약에 있다면 또 한가지 확인 과정을 거쳐야 하는데, 이전에 나왔던 사람들도 모두 원소로 갖고 있는지를 확인해보아야 한다. 예를 들어서 줄이 {3 1 2}형태로 서 있다고 해보자. 여기서 정보로 (3,2)가 들어왔다고 한들, 사이에 1이 가로막고있기 때문에 last인 2는 한 칸도 앞으로 움직일 수 없다. 따라서 3이 1과 교환할 수 있는 여지를 확인해본다는 의미이고 set[3]의 원소로 1이 있는지 확인해본다는 것이다. 따라서 정보로 교환될 수 없는 사람들을 별도로 저장하는 벡터인 v를 설정하고, 교환할 수 없을 때마다 v에 추가해야 한다.

주의할 점 : 

-

배울 점 : 

난이도 1800문제 중에서 수학적으로 연산을 취하는 것들은 나름 접근을 하겠는데, 이 문제처럼 수학보다는 아이디어적 접근을 하는 문제는 아직까지 약한 것 같다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
priority_queue<int,vector<int>,greater<int>> mpq;
const int SPACE=0,NL=1;  string exm;
inline void showAll(vector<int> &v,int sep){ //0=space,1="\n"
    for(int &here:v) printf("%d%c",here,(sep)?'\n':' '); }
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
inline vector<int> int_seperation(int N,int d=10){
    vector<int> v; while(N){v.push_back(N%d); N/=d;}
    reverse(v.begin(),v.end()); return v; }
/*********************Contest Template***********************/
const int SIZE= 300009;
int order[SIZE];
set<int> si[SIZE];
 
int main(){
    int n,m;    scanf("%d %d",&n,&m);
 
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&order[i]);
    }
 
    while(m--){
        int a,b;    scanf("%d %d",&a,&b);
        si[a].insert(b);
    }
 
    vector<int> v;
    int last=order[n],ans=0;
    for(int i=n-1 ; i>=1 ; i--){
        int cur=order[i];
        bool possible=false;
        if(si[cur].count(last)){
            possible=true;
            for(int here:v){
                if(si[cur].count(here)==0){
                    possible=false;
                }
            }
        }
 
        if(possible) ans++;
        else v.push_back(cur);
    }
    printf("%d\n",ans);
 
    return 0;
}
/*
 
*/