[백준OJ] 14595번 동방 프로젝트 (Large)

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

14595번: 동방 프로젝트 (Large)

---

 

풀이

먼저 빅-종빈 빌런이 문을 뿌수는 행동을 입력받은것들을, 시작 방을 기준으로 오름차순 정렬을 해준다.

그런뒤 처음 종빈 빌런이 뿌수는 방을 left와 right에 저장을 해둔뒤, 다음오는 행동의 시작방이 right보다 작거나 같으면, 지금 부수고 있는 방과 한방으로 합쳐지므로, right를 갱신해준다.

 

만약 다음행동의 시작방이 right보다 크다면, right와 시작하는 방 사이에 단독으로 살아있는방이 존재하므로, 존재하는 방들을 더해준뒤, left와 right를 갱신시켜주면된다.

 

예제 3번을 예시로 들어보겠다.

초기상태

 

오름차순으로 정렬이 되어있으므로, 첫번째 행동(1~3번사이의 벽을 부숨) 을 한다면 아래의 사진과 같다.

1~3 break

 

다음 행동(2~4번 사이의 벽을 부숨) 을 실행하면, 2~3 사이의 벽은 이미 부서져 있으므로, 3~4 사이의 벽을 부수면 된다. 이렇게 부수면, 위의 행동을 했을때와 방이 합쳐지므로 아직까지 나온 방은 1개이다.

 

다음행동 (5~8번 사이의 벽을 부숨) 을 실행하면, 이전에 합쳐졌던 방과는 다른 방이 만들어지므로, 방의 개수와 left,right를 갱신해준다. 만약 6~8번사이의 벽을 부수라고 했으면, 중간에 5번방이 단독으로 살아있게된다. 이것을 고려해서 방의 개수를 갱신해준다.

 

행동이 모두 끝난후, right+1~N번방까진 모두 단독으로 살아있는 방들이므로, 방의 개수를 업데이트해준다.

 

 

이때 주의를 해주어야할것은, 무조건 1번방부터 시작한다는 조건이 없으므로, 처음 부수기전 앞에 단독으로 살아있는 방들의 개수도 고려해주면 된다.

 

시간복잡도

M개의 종빈빌런 행동을 정렬하는데 O(MlogM)시간이 걸린다.

다음으로 방이 몇개 살아있는지에 대해 검사하는건, 모든 행동을 한번만 탐색하면되므로 O(M)이 된다.

따라서 O(MlogM)이 된다.

 

반응형

 

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef pair<int,int> pii;

int n,m;
vector<pii> v;

int main() {
    cin>>n>>m;
    /*
    만약 빅 종빈이 행동하지 않으면
    모든 방은 살아있으므로
    방 개수 출력
    */
    if(m==0){
        cout<<n<<"\n";
        return 0;
    }
    
    //빅 종빈의 행동 입력
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        v.push_back({a,b});
    }
    //시작방 기준 오름차순 정렬
    sort(v.begin(),v.end());
    
    
    //처음 행동을 시작하는 방과 끝방 선언
    int left=v[0].first;
    int right=v[0].second;
    int ret;
    
    /*
    만약 처음시작하는 방이 1번방이면, 초기 방의 개수는 1개가되고,
    아니라면, 1~ (left-1) 번방들은 모두 단독으로 살아있고,
    left~right로 합쳐진 방이 1개 있으므로, 초기 방의 개수는 left개가 된다.
    */
    if(left==1){
        ret=1;
    }
    else{
        ret=left;
    }
        

    for(int i=1;i<m;i++){
        //다음행동이 left와 right사이에 있으면 합쳐지므로 right갱신
        if(v[i].first<=right){
            right=max(right,v[i].second);
        }
        //아니면 방의 개수, left,right 갱신
        else{
            ret+=(v[i].first-right);//갱신할때 사이에 단독으로 살아있는방들 고려
            left=v[i].first;
            right=v[i].second;
        }
    }
    
    //행동이 끝났을때 마지막방이 아니라면, right+1~N번방의 개수를 추가
    if(right!=n){
        ret+=(n-right);
    }
    cout<<ret;
    
	return 0;
}