[ 백준 C++ ] 2170번 선 긋기

문제 

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

2170번: 선 긋기

 

처음 아이디어 

 

시작점, 끝 점 이용 

처음 입력한 두 점을 
시작점, 끝 점에 넣는다. 
linear 시작점에 첫 시작점을 넣어준다. 

다음 시작점이 시작점과 끝 점 사이라면 계속 진행 
아니라면 끝점 - 처음 시작점을 cnt에 넣어주고 
linear 시작점에 다음 시작점을 넣는다. 



예제로 보면 
( 1 , 3 )
시작점 : 1 , 끝 점 : 3  linear시작점 : 1  cnt : 0 
( 2, 5 )
새로운 시작점이 1<= 2 <=3 
시작점 : 2    끝 점 : 5 linear시작점 : 1 cnt : 0
( 3, 5 ) 
새로운 시작점 3 은 2<= 3 <=5 
시작점 : 3 , 끝 점 : 5  linear시작점 : 1  cnt : 0
( 6, 7 ) 
새로운 시작점 보다 큼 
cnt : 끝 점(5) - 처음 시작점 (1) = 4 
시작점 6 : 끝 점 : 7 ,cnt : 4
linear시작점 : 6 
만약 끝이라면 끝 점 - 시작점 7-6 = 1 
cnt에 더한다. cnt : 4+1 = 5 

인데 무조건 적은수 부터 들어오지 않으니 입력받고 정렬 

 

다른 사람 코드 참고해서 더 깔끔하게 변경 

 

코드 

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

using namespace std; 

int n;

vector<pair <int,int>> arr;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
   
    for(int i=0; i<n; i++)
    {
        int a,b=0; 
        cin >> a >>b;
        arr.push_back(make_pair(a,b));
    }
    sort(arr.begin(), arr.end()); //오름차순으로 정렬
    
    int ans =0;
    
    int start = arr[0].first;
    int end = arr[0].second;
    
    for(int i=1; i<n; i++)
    {
        int s = arr[i].first;
        int e = arr[i].second;
        
        if(end <=s)
        {
            ans += end - start;
            start = s;
            end = e;
        }else
        {
            if(end < e)
            {
                end = e;
            }
        }
        
        
    }
    ans += end - start;
    cout << ans << "\n";
    
    return 0;
    
}

 

코딩테스트 보면서 비슷한 문제 많이 본것같다. 처음에 집중못해서 길이 구해야하는데 선 갯수구하고 있었다.