[백준][C++] 2024 선분 덮기

www.acmicpc.net/problem/2024

2024번: 선분 덮기

 

 

 

알고리즘 종류

    - 자료구조

 

 

사고 과정

    - 현재 시점을 기준으로 다음에 들어올 시작점이 현재 시점 이하이면서 최대 끝지점을 찾으면 된다. 아래 예시를 보자.

       

    - m=10이고 7개의 선분들이 있다. 그려보면 아래와 같다.

 

 

 

    1. 현재 시점 0을 기준으로 0이하인 시작점을 가지는 선분들은 [0, 1]과 [0, 5]이다. 이중에서 가장 큰 끝지점을 갖는 것은 [0, 5]이다. 시작점을 0에서 5로 바꿔준다.

    1-1. 선분[2, 4]는? 최대 끝지점이 5로 정해지고 선분 [2, 4]가 들어왔다. 최대 끝지점이 5보다 작으므로 무시한다.

 

    2. 현재 시점 5를 기준으로 5이하인 시작점을 가지는 선분들은 [3, 6], [4, 8]이다. 이중에서 가장 큰 지점을 가진 선분은 [4, 8]이다. 시작점을 5에서 8로 바꿔준다.

    2-1. 선분 [7, 8]도 마차간지로 무시하고 넘어간다.

 

    3. 현재 시점 8을 기준으로 8이하인 시작점을 가지는 선분은 [7, 10]이다. 목표지점 10에 도달했으므로 선분 [0, 10]을 3개의 선분으로 덮을 수 있다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<pair<int,int> > v;
int m;
int answer=0;
 
 
bool cmp(pair<int,int> a,  pair<int,int> b){
    if(a.first == b.first){
        return a.second < b.second;
    }
    return a.first < b.first;
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> m;
    
    int l, r;
    while(true){
        cin >> l >> r;
        
        // 시작과 끝의 조건을 절대값으로 안내되어서 아래와 같이 조정이 필요  
        if(l>r){
            int tmp = l;
            l = r;
            r = tmp;
        }
        
        if(l==0 && r==0) break;
        if(r<0 || l>m || l==r) continue;
        
        v.push_back({l, r});
    }
    
    // 시작점 오름차순, 끝점 오름차순  
    sort(v.begin(), v.end(), cmp);
    
    int cur = 0;
    int idx = 0;
    
    while(true){
        
        int maxNum = -1;
        
        for(; idx<v.size(); idx++){
            if(v[idx].first <= cur){ // 다음에 들어오는 값이 현재 지점 이하인가  
                if(v[idx].second > maxNum) // 저장된 최대 끝지점 보다 큰 가? 
                    maxNum = v[idx].second;
            }
            else break;    
        }
        
        // 다음에 들어오는 시작점이 현재 시작점을 포함하지 못하므로 선분을 덮을 수 없음  
        if(maxNum == -1){
            cout << "0" << endl;
            break;
        }
        
        answer ++;
        if(maxNum >= m){
            cout <<  answer << endl;
            break;
        }
        // 시작점을 최대 끝지점으로 변경  
        cur = maxNum;
    }
}

 

 

 

시행착오

    - 라인 스위핑 문제일 것 같아서 우선순위 큐를 사용하려고 시도했다. 그런데 막상 관찰해보니 현재시점을 포함하는 선분들 중에 오른쪽 최대값을 찾으면 될 것 같았다. 더 가볍게 풀기 위해서 많은 문제를 생각해보면서 풀어야 겠다.