[2170번] 선 긋기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Map STL :: http://www.crocus.co.kr/604

2. 구현

이 문제는 선을 긋는데 중복된 선은 하나의 선으로 계산하여 선의 길이가 최대 몇인지 계산하는 문제이다.

우선적으로 입력 받은 선의 좌표를 모두 Map에 pair로 넣어준다. 이렇게 된다면 시작 좌표를 기준으로 Map에서 정렬되어있다.

그리고 맵에서 하나씩 꺼내며 아래와 같이 조건을 형성시킨다.

이때 sTmp와 eTmp가 start보다 작은 조건은 없는데 start보다 절대 작을수는 없다.

그 이유는 Map 자체에서 하나씩 차례대로 뽑을 때 x좌표가 정렬되어 있기 때문에

그 다음 것을 뽑게 된다면 x좌표가 크거나 같은 것 밖에 나오지 않게 된다.

선 길이의 합을 구하는 것은 겹쳐서 선이 계속 나타난다면 갱신, 다음 값을 뽑았을 때 이전 끝점보다 큰 시작점이 나오면

이전 선의 길이를 sum에 더해주는 방식으로 진행하면 된다.

소스 코드 : 

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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

#include <iostream> #include <cstdio> #include <map>   using namespace std;   typedef pair<int, int> pii;   map<pii, int> mp;   int main() {     int tc;     scanf("%d", &tc);       // 입력이 1개뿐이면 그냥 m - n     if (tc == 1)     {         int n, m;         scanf("%d %d", &n, &m);         cout << m - n;         return 0;     }       // map에 n, m값을 모두 넣어준다.     // n기준으로 오름차순 정렬     while (tc--)     {         int n, m;         scanf("%d %d", &n, &m);           mp[{n, m}] = 1;     }       // 첫 시작값과 끝 값을 넣어준다.     auto it = mp.begin();     int start =    it->first.first;     int end = it->first.second;     it++;       long long sum = 0;     for (it; it != mp.end(); it++)     {         int sTmp = it->first.first;         int eTmp = it->first.second;           // 새로 들어온 시작 값이 start와 end 사이 있을 경우         if (start <= sTmp && sTmp <= end)         {             // 새로 들어온 끝 값이 end보다 크면             // end를 갱신             if (eTmp > end)                 end = eTmp;         }           // 새로 들어온 start가 end보다 클 때         else if (sTmp > end)         {             // 기존에 존재하던 start와 end를 sum에 계산해준다.             sum += end - start;             // 갱신             start = sTmp;             end = eTmp;         }           // map의 마지막 부분에 왔는지 확인하고         // 마지막 부분이라면 값을 계산해주고 종료         if (++it == mp.end())         {             sum += end - start;             break;         }         it--;     }       cout << sum;     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus