본문 바로가기
알고리즘/백준

[cpp 알고리즘] 백준 2170 선 긋기

by sum_mit45 2024. 11. 11.
728x90
반응형

[백준] 2170 선 긋기 cpp(c++) 풀이

알고리즘: 정렬, 스위핑

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

문제 요약

- 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다.

- 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다. (=> 선이 여러번 그련진 곳은 한 번씩만 계산한다.)

- 이와 같은 식으로 선을 그었을 때, 그려진 선들의 총 길이를 구하는 프로그램 작성하기.

풀이 정리

- vector<pair<int,int>> 를 활용하여 각 점의 (시작점, 끝점)을 저장하였다. 

- 그리고 선을 그을 때, 인접한 두 선이 이어지는지 확인하기 위해 sort 를 활용해 정렬했다. 

- 이전 선의 시작점 <=  다음 선의 시작점 <= 이전 선의 끝점인 경우에 이어질 수 있다고 판단했다. (아래 예제를 보면 왜 등호를 포함하는지도 알 수 있다.) 그럼 이전 선의 시작점부터 max(이전 선의 끝점, 다음 선의 끝점)을 끝점으로 선이 이어진다.

- 따라서 이렇게 새로 만든 이어진 선을 v2에 넣어주고, v2에 있는 선들을 (끝점-시작점)의 합으로 총 길이를 구했다. 

 

백준 2170 풀이

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define ll long long
using namespace std;

ll N;

vector<pair<int,int>> v;
vector<pair<int,int>> v2;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    for(int i=0; i<N; i++){
        ll start, end; cin >> start >> end;
        v.push_back({start, end});
    }
    
    sort(v.begin(), v.end()); //오름차순정렬
    
    ll temp1, temp2;
    temp1 = v[0].first;
    temp2 = v[0].second;
    for(int i=1; i<N; i++){
        if(temp1 <= v[i].first && v[i].first <= temp2){
            if(v[i].second > temp2){
                temp2 = v[i].second;
            }
        }
        else{ //다음값이 더 크면
            v2.push_back({temp1, temp2});
            temp1 = v[i].first;
            temp2 = v[i].second;
        }
    }
    v2.push_back({temp1, temp2});
    
    ll ans = 0;
    for(int i=0; i<v2.size(); i++){
        ans += (v2[i].second - v2[i].first);
    }
    cout << ans;
    return 0;
}
728x90
반응형