관리 메뉴

차근차근

[백준 2170] 선 긋기 본문

대학교/Algorithm

[백준 2170] 선 긋기

SWKo 2020. 2. 15. 03:24

0. 제목

  • 백준 2170 선 긋기
  • BOJ 2170 선 긋기
  • C++ 2170 선 긋기

1. 문제

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


2. 풀이

  • 먼저 from, to N쌍을 입력받는다.
  • 그 후 from을 기준으로 정렬을 한다.
  • 그럼 선끼리 겹치는 선들이 있을 것이고 겹치지 않는 선들이 있을 것이다.
  • 겹치지 않는 경우에는 현재 길이에 l-r 만큼 더해주면 되고 겹치는 경우에는 오른쪽 끝을 다음 번 오른쪽 끝으로 갱신시켜주면 된다.
  • 반복문이 끝난 후에는 마지막으로 갱신된 l-r을 더해주면 답이 나온다.
  • 주의할 점은 이 문제에서 N과 선택한 지점의 범위가 크다. 따라서 main함수의 첫 세줄을 추가 하지 않았을 때는 시간초과로 떴다.
  • 저 세줄을 추가하면 정답처리가 된다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>
using namespace std;
 
typedef pair<intint> P;
P L[1000001];
int N;
int from, to;
int l, r;
int ans = 0;
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> from >> to;
        L[i] = P(from, to);
    }
    sort(L, L+N);
    l = L[0].first;
    r = L[0].second;
    
    for(int i = 1; i < N; i++){
        if(L[i].first > r){//안겹치는 경우
            ans += r-l;
            l = L[i].first;
            r = L[i].second;
        }
        else if(L[i].first < r && L[i].second > r){//겹치는 경우
            r = L[i].second;
        }
    }
    ans += r-l;
    
    cout << ans << '\n';
    
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 4963] 섬의 개수  (0) 2020.02.16
[백준 1966] 프린터 큐  (0) 2020.02.16
[백준 1699] 제곱수의 합  (0) 2020.02.15
[백준 1149] RGB거리  (0) 2020.02.13
[백준 11650] 좌표 정렬하기  (0) 2020.02.13
0 Comments
댓글쓰기 폼