아우으 우아으이야!!( BOJ 15922 )

문제 : https://www.acmicpc.net/problem/15922

15922번: 아우으 우아으이야!!

 

문제 파악하기

N개의 선분을 수직선 위에 그렸을 때, 그어진 모든 선분의 길이의 합을 구하는 문제입니다. 입력에 따라 선분들이 겹치는지 확인할 필요가 있습니다. 다행히 선분의 개수가 100,000개이기 때문에 충분히 정렬을 사용할 수 있습니다.

 

문제 해결하기

모든 선분을 왼쪽 좌표 기준으로 정렬하면 가장 왼쪽에 위치한 선분부터 탐색을 시작할 수 있습니다. 가장 왼쪽의 선분의 왼쪽과 오른쪽을 각각 (l, r)으로 설정할 수 있으며, 다음 선분부터 하나씩 (l, r)과 겹치는지 확인하면 됩니다. 만약 현재 확인할 inp[i] 선분이 (l, r)과 겹친다면 inp[i] 선분을 포함할 수 있게 (l, r)을 갱신하며, 만약 겹치지 않는다면 지금까지 구한 선분의 길이(r-l)만큼을 정답에 더해주고 새롭게 선분을 (inp[i].first, inp[i].second)로 만들면 됩니다. 잊지 말아야 할 점은 항상 마지막에도 선분을 더해주어야 합니다. 문제를 해결하는 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
#define PAIR pair<int, int>
using namespace std;
 
int N, x, y;
vector< PAIR > inp;
 
int l, r, ret;
 
int main() {
    scanf("%d", &N);
    for(int i=1;i<=N;i++) {
        scanf("%d %d", &x, &y);
        inp.push_back({x, y});
    }
 
    sort(inp.begin(), inp.end());
 
    l = inp[0].first; r = inp[0].second;
    for(int i=1;i<N;i++) {
        if(inp[i].first <= r) {
            if(inp[i].second <= r) continue;
            else r = inp[i].second;
        }
        else {
            ret += (r-l);
            l = inp[i].first;
            r = inp[i].second;
        }
    }
    ret += (r-l);
 
    printf("%d", ret);
}

후기

기본적인 스위핑 문제입니다. 다만, 선분의 겹침 판별은 자주 나오는 유형이기 때문에 알고리즘을 익힐 때, 추천할만한 문제입니다.