백준 2283 줄세우기
2283번: 구간 자르기
1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다. 2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다.
www.acmicpc.net
문제 설명
- 수직선 상 구간 N개가 있다.
- 임의의 두 정수 A, B(A<B)를 정하여, 각 구간에서 A와 B 사이에 포함되지 않은 부분을
모두 잘라냈을 때 남는 부분들의 길이의 총합이 K가 되도록 하여라.
- 두 정수 A, B를 출력한다. 조건을 만족하는 A, B가 존재하지 않으면 "0 0"을 출력한다.
조건을 만족하는 A, B가 여러 개 존재할 때는 A가 가장 작은 경우를 출력한다.
그것도 여러 개 존재할 때는 B가 가장 작은 경우를 출력한다.
입력 값
- 1번째 줄에 정수 N, K 가 주어진다.
( 1 <= N <= 1,000 / 1 <= K <= 1,000,000,000 )
- 2-N+1 번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다.
양 끝점의 위치는 0이상 1,000,000 이하의 정수이다.
예제
문제 분석
- 이 문제를 간단하게 정의하면, 구간 사이의 수직선의 길이의 합이 K인 구간을 찾는 방법이다.
- 두 구간 사이를 살펴보는 문제이기 때문에 투포인터를 이용하면 간단하게 풀 수 있다.
투 포인터, 슬라이딩 윈도우 기법
투 포인터(Two Pointers method) 투 포인터란? - 배열을 따라 두 개의 포인터를 이동시키면서 데이터를 처리하는 알고리즘 - 포인터 두 개는 모두 한쪽 방향으로 움직인다. - 투 포인터를 이용한 경
9327144.tistory.com
- 문제 풀이 과정은 다음과 같다.
1. 두 범위 start와 last가 0부터 시작한다.
2. start와 last 사이의 수직선의 길이의 합(SUM)과 K를 비교한다.
3. SUM > K 인 경우 수직선을 줄여야 하기 때문에 start++를 하고 SUM을 구한 후 2번으로 돌아간다.
4. SUM < K 인 경우 수직선을 늘려야 하기 때문에 last++를 하고 SUM을 구한 후 2번으로 돌아간다.
5. SUM == K 인 경우 정답이 되기 때문에 종료한다
- start++가 일어났을 때 SUM을 구하는 방법은 다음과 같다.
0. start가 지나간 범위의 수직선의 종료 값을 우선순위큐에 넣는다.
1. start++가 일어났다면, 해당 값보다 작은 값을 우선순위큐에서 제거한다.
2. 우선순위큐에 남아 있는 값은 start++가 일어나면서 줄어든 값이기 때문에
그 값 만큼 SUM에서 제거한다.
3. start++ 후 그 값을 시작으로 하는 수직선을 우선순위 큐에 넣는다.
- last++가 일어났을 때 SUM을 구하는 방법은 다음과 같다.
0. last가 지나간 범위의 수직선의 종료 값을 우선순위큐에 넣는다.
1. last++가 일어났다면, 해당 값보다 작은 값을 우선순위큐에서 제거한다.
2. 우선순위큐에 남아 있는 값은 last++가 일어나면서 늘어난 값이기 때문에
그 값 만큼 SUM에서 더해준다.
3. last++ 후 그 값을 시작으로 하는 수직선을 우선순위 큐에 넣는다.
- 주의할 점은 범위를 찾을 수 없는 경우 0 0을 리턴해야 한다는 점이다.
소스 코드
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, K;
int sum = 0;
cin >> N >> K;
vector<pair<int, int>> node;
for (int i = 0; i < N; i++) {
int a, b;
cin >> a >> b;
node.push_back({ a,b });
}
sort(node.begin(), node.end());
int start = 0;
int last = 0;
int startIndex = 0;
int lastIndex =0 ;
priority_queue<int,vector<int>,greater<int>> startPQ;
priority_queue<int,vector<int>,greater<int>> lastPQ;
for (int i = 0; i < node.size(); i++) {
if (node[i].first == 0) {
startPQ.push(node[i].second);
lastPQ.push(node[i].second);
startIndex = i+1;
lastIndex = i + 1;
}
else {
break;
}
}
sum = 0;
while (last <= 1000000) {
if (sum > K) {
start++;
while (!startPQ.empty()) {
if (startPQ.top() < start) {
startPQ.pop();
}
else {
break;
}
}
sum -= startPQ.size();
for ( startIndex; startIndex < node.size(); startIndex++) {
if (node[startIndex].first <= start) {
startPQ.push(node[startIndex].second);
}
else {
break;
}
}
}
else if (sum == K) {
break;
}
else {
last++;
while (!lastPQ.empty()) {
if (lastPQ.top() < last) {
lastPQ.pop();
}
else {
break;
}
}
sum += lastPQ.size();
for (lastIndex; lastIndex < node.size(); lastIndex++) {
if (node[lastIndex].first <= last) {
lastPQ.push(node[lastIndex].second);
}
else {
break;
}
}
}
}
if (last == 1000001) {
last = 0;
}
cout << start << " " << last << endl;
return 0;
}
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
[BOJ-1916] 최소비용 구하기(C++) (0) | 2021.07.14 |
---|---|
[BOJ-2325] 개코전쟁(C++) (0) | 2021.07.13 |
[BOJ-2252] 줄 세우기(C++) (0) | 2021.07.09 |
[BOJ-2098] 외판원 순회 (C++) (0) | 2021.07.08 |
[BOJ-1939] 중량제한 (C++) (0) | 2021.07.07 |
댓글