728x90
반응형
[백준] 2170 선 긋기 cpp(c++) 풀이
알고리즘: 정렬, 스위핑
https://www.acmicpc.net/problem/2170
문제 요약
- 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다.
- 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다. (=> 선이 여러번 그련진 곳은 한 번씩만 계산한다.)
- 이와 같은 식으로 선을 그었을 때, 그려진 선들의 총 길이를 구하는 프로그램 작성하기.
풀이 정리
- vector<pair<int,int>> 를 활용하여 각 점의 (시작점, 끝점)을 저장하였다.
- 그리고 선을 그을 때, 인접한 두 선이 이어지는지 확인하기 위해 sort 를 활용해 정렬했다.
- 이전 선의 시작점 <= 다음 선의 시작점 <= 이전 선의 끝점인 경우에 이어질 수 있다고 판단했다. (아래 예제를 보면 왜 등호를 포함하는지도 알 수 있다.) 그럼 이전 선의 시작점부터 max(이전 선의 끝점, 다음 선의 끝점)을 끝점으로 선이 이어진다.
- 따라서 이렇게 새로 만든 이어진 선을 v2에 넣어주고, v2에 있는 선들을 (끝점-시작점)의 합으로 총 길이를 구했다.
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
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[cpp 알고리즘] 백준 3474 교수가 된 현우 (1) | 2024.11.10 |
---|---|
[cpp 알고리즘] 백준 17827 달팽이 리스트 (0) | 2024.11.09 |
[cpp 알고리즘] 백준 20005 보스몬스터 전리품 (2) | 2024.11.08 |
[cpp 알고리즘] 백준 15721 번데기 (0) | 2024.08.06 |
[cpp 알고리즘] 백준 1080 행렬 (1) | 2024.07.22 |