Algorithm/Baekjoon
[Algorithm] Baekjoon 2170번 : 선 긋기
MaxLevel
2023. 6. 15. 02:01
https://www.acmicpc.net/problem/2170
2170번: 선 긋기
첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.
www.acmicpc.net
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
|
struct Node
{
int start;
int end;
};
vector<Node> nodes;
int n;
bool cmp(const Node& a, const Node& b)
{
return a.start < b.start;
}
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i)
{
Node node;
cin >> node.start >> node.end;
nodes.push_back(node);
}
sort(nodes.begin(), nodes.end(), cmp);
int start = nodes[0].start;
int end = nodes[0].end;
int answer = 0;
for (int i = 1; i < nodes.size(); ++i)
{
if (nodes[i].start <= end)
{
if (end < nodes[i].end)
{
end = nodes[i].end;
}
}
else
{
answer += end - start;
start = nodes[i].start;
end = nodes[i].end;
}
}
cout << answer + end - start;
return 0;
}
|
cs |
프로그래머스에서 호텔 대실문제를 풀다가, 관련되서 내가 잘 모르는부분이 있다는 것을 깨닫고 알아보다가 라인스위핑이란 풀이방법이 있다는것을 인지. 대표적인 문제로 이 선긋기 문제가 나와서 풀어봤다.
이걸 다시 호텔대실문제에 대입해봐야겠다.