링크 : https://www.acmicpc.net/problem/15922
문제 설명
수직선상에 선분(x1~x2)을 순차적으로 최대 10만개 까지 입력해줍니다.
이 때 입력되는 데이터는 좌표가 x가 증가하는 순으로, x가 같다면 y가 증가하는 순으로 주어집니다.
N개의 선분을 모두 그렸을 때, 수직선 위에 그어진 선분의 길이의 총합을 구하시오.
아이디어
● 선분은 모두 정렬된 상태로 주어져, 다음 선분이 겹치는지 안겹치는지 계속 확인하며 나아가면 선분을 겹쳐서 연결되는 긴 선분 하나로 취급할 수 있을 것 같습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
if(N == 1)
{
int x, y;
cin >> x >> y;
cout << y - x;
return 0;
}
vector<pair<int, int>> v(100001);
for(int i = 0; i < N; ++i)
{
int x, y;
cin >> x >> y;
v[i] = {x, y};
}
int ans = 0;
int i = 0;
while(i < N)
{
int s = v[i].first;
int e = v[i].second;
while(i+1 < N && e > v[i+1].first)
{
++i;
e = e < v[i].second ? v[i].second : e;
}
ans += e - s;
i++;
}
cout << ans;
return 0;
}
'알고리즘' 카테고리의 다른 글
BOJ(16936) - 나3곱2 (0) | 2024.06.24 |
---|---|
백준(5430) - AC (0) | 2024.06.14 |
프로그래머스 - 기지국 설치 (0) | 2024.05.29 |
프로그래머스 - 파일명 정리 (0) | 2024.05.28 |
프로그래머스 - 방문길이 (0) | 2024.05.27 |