BOJ 15922, 아우으 우아으이야!!
ProblemSolving ·이번 문제는 라인 스위핑 관련 문제같습니다.
풀이
처음 이 문제를 봤을 때 어떻게 풀어야할 지 막막했는데 입력이 굉장히 친절하게 들어오는 걸 보고 바로 풀었습니다.
(좌표는 x가 증가하는 순으로, x가 같다면 y가 증가하는 순으로 주어진다)
이전의 좌표와 현재의 좌표들만 비교하면 정답을 구할 수 있습니다.
이전에 오른쪽 좌표가 현재 왼쪽 좌표보다 큰 경우만 잘 처리해주시면 됩니다.
(이전 오른쪽의 좌표 - 현재 왼쪽의 좌표) 값을 sum 값에서 빼주면 되겠죠? 그런데 현재 오른쪽 좌표보다 이전의 오른쪽 좌표가 더 큰 경우더 있을 수있습니다. 이때는 그냥 이번 줄이 이전줄의 포함되는 경우이기 때문에 이번줄에서 sum자체를 취소하시면 됩니다.
그리고 또 하나 중요한게 이전 왼쪽 좌표와 오른쪽 좌표를 설정하는 것 입니다.무턱대고 현재 오른쪽 좌표를 이전 오른쪽 좌표로 하시면 안됩니다.
이전 오른쪽 좌표랑 현재 오른쪽 좌표중 가장큰 것이 이전 오른쪽 좌표로 현재 왼쪽 좌표와 이전 오른쪽 좌표중에 큰 것이 이전 왼쪽 좌표로 해주셔야
다음 선분은 받아들일 때 빈 공간이 생기지 않습니다.
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
int n, lef, rig, blef, brig,sum;
int main()
{
scanf("%d", &n);
scanf("%d %d", &lef, &rig);
sum += (rig - lef);
brig = rig, blef = lef;
for (int i = 2; i <= n; i++)
{
scanf("%d %d", &lef, &rig);
sum += (rig - lef);
if (brig > lef)
{
if (brig > rig)
sum -= (rig - lef);
else
sum -= (brig - lef);
}
brig = max(brig,rig), blef = max(brig,lef);
}
printf("%d", sum);
return 0;
}