백준 알고리즘 2170,15922번 : 선 긋기,아우으 우아으이야!!

Zoo Da·2021년 8월 19일
0

백준 알고리즘

목록 보기
168/337
post-thumbnail

링크

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

풀이 코드(C++)

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define MAX 1001
#define sz(a) int((a).size())
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using wector = vector<vector<int>>;

const int INF = int(1e9) + 1;

// Sweeping
int main(){
  fastio;
  int n; cin >> n;
  vector<pii> v(n);
  for(int i = 0; i < n; i++) cin >> v[i].X >> v[i].Y;
  // 선분들을 왼쪽 끝 좌표 순으로 정렬
  sort(v.begin(), v.end()); 
  // [l,r] : 현재 합치고 있는 구간
  int sum = 0,st = -INF,en = -INF;
  for(int i = 0; i < n; i++){
    // 현재 구간과 선분이 합쳐질 수 없음.
    if(en < v[i].X){
      // 결과에 더함
      sum += en - st;
      // 현재 구간을 이번 선분으로 초기화
      st = v[i].X;
      en = v[i].Y;
    }
    // 합쳐짐 : 현재 구간의 r을 늘를 수 있으면 늘린다.
    en = max(en, v[i].Y);
    // 마지막 구간도 결과에 더해줌.
    if(i == n - 1) sum += en - st; 
  }
  cout << sum << "\n";
  return 0;
}

풀이

두 문제 모두 같은 코드로 풀 수 있습니다.

참고

https://m.blog.naver.com/kks227/220907708368

profile
메모장 겸 블로그

0개의 댓글