https://www.acmicpc.net/problem/10000
10000번: 원 영역
문제 x축 위에 원이 N개 있다. 원은 서로 교차하지 않는다. 하지만, 접할 수는 있다. 원으로 만들어지는 영역이 몇 개인지 구하는 프로그램을 작성하시오. 영역은 점의 집합으로 모든 두 점은 원을 교차하지 않는 연속되는 곡선으로 연결될 수 있어야 한다. 입력 첫째 줄에 원의 개수 N(1 ≤ N ≤ 300,000)이 주어진다. 다음 N개 줄에는 각 원의 정보 xi와 ri가 주어진다. xi는 원의 중심 좌표이며, ri는 반지름이다. (-109 ≤ xi ≤ 1
www.acmicpc.net
문제해설
"라인 스위핑"을 염두에둔 상태에서 문제를 잘 읽으면
조건에 의해 풀 수있는 방법이 떠오르는 문제이다( 저는 상당히 오래걸렸습니다 ㅠ )
위의 빨간박스가 이문제의 핵심이며 라인스위핑을 통해서 답을 구해낼 수 있는 이유라고 할 수 있습니다.
쉽게 생각해서
원의 왼쪽 : 스택의 왼쪽괄호
원의 오른쪽 : 스택의 오른쪽괄호
라고 생각하면 됩니다.
왼쪽괄호가 열렸다는 것은 언젠가 자신보다 오른쪽 좌표에서 오른쪽 괄호가 나타난다는 것을 의미합니다.
스택의 열고 닫기를 하는 와중에 닫는 동작을 할 때에, 중간에 구멍없이 계속 접해왔는지 확인화면 되는 문제입니다.
< 스택 >
class stackItem {
public:
ll pos; int state;
stackItem(ll pos, int state) {
this->pos = pos;
this->state = state;
}
}; stack<stackItem> st;스택에 pos와 state 라는 변수를 두었습니다.
pos : 좌표값을 의미합니다.
state
초기 괄호를 열였을 경우 : 0
열고나서 끊김없이 계속 접해온경우 : 1
열고나서 끊긴 적이 있는경우 : -1
의 세가지의 경우를 나누었습니다.
여러 케이스를 통해 예시를 들어 보겠습니다
< 예시 1 >
위 처럼 원이 하나만 존재하는 경우는 괄호로 표현시 () 가 됩니다.
위와 같이 stack에 state 0 이 들어가게되고
) 에 의해 pop이 되는경우 ans++ 를 해주게 됩니다.
< 예시 2 >
위와같이 큰원 안에 작은원이 두개가 완전히 접한다고 가정해봅시다
괄호로 표현하면 (()()) 가 될 것입니다. 위 그림이 어떻게 답이 5가 되는지 확인 해봅시다.
위의 왼쪽 괄호 (( 두개를 처리한뒤의 스택의 모습입니다. 물론 pos 정보도 포함하고 있겠죠.
top 에있는 item은 방금 스택에 들어간 item이고
그밑의 item은 push되는 item과 좌표값이 겹치기 때문에 state가 1로 변경된 item입니다.
그다음 ) 가 들어갔을 경우는 ( ) 가 짝이 지어짐으로 pop이 되고, state가 0 이였으므로 ans++를 해주게 됩니다.
똑같이 그다음 ) 가 들어갔을 경우는 ( ) 가 짝이 지어짐으로 pop이 되고, state가 0 이였으므로 ans++를 해주게 됩니다.
마지막의 경우는 state가 1인 상태임으로 답이 2가 나오게 됩니다.
총합 답이 5가 나오게 됩니다.
< 예시 3 >
위의 그림의 경우는 스택의 모양으로는 ( ()() ) 가 될 것입니다. 예시 2과 스택의 구조는 같지만
item의 state를 변경해줌으로써 다른 답이 나오게 됩니다.
아까와 다르게 밑의 item의 state가 -1이 된 모습을 확인할 수 있습니다.
처리하는 과정은 ( 괄호를 추가하였을때 top 에있는 pos와 현재 pos와 다르다면
top에있는 item의 state를 -1로 바꾸어 주었습니다.
그후 현재 정보를 push 해주면 됩니다.
이후 부터는 예시2와 같이 처리해주면 답이 4가 나오게 됩니다.
전체코드
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
bool cmp(pll a, pll b) {
if (a.first == b.first) return a.second > b.second;
else return a.first < b.first;
}
class stackItem {
public:
ll pos; int state;
stackItem(ll pos, int state) {
this->pos = pos;
this->state = state;
}
}; stack<stackItem> st;
vector<pair<ll, int>> vec;
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int N; cin >> N;
for (int i = 0; i < N; i++) {
ll x, r; cin >> x >> r;
vec.push_back({ x - r,-1 });
vec.push_back({ x + r, 1 });
}
sort(vec.begin(), vec.end(), cmp);
ll ans = 0; ll last = 0;
for (int i = 0; i < vec.size(); i++) {
if (st.empty()) {
st.push(stackItem(vec[i].first, 0));
last = vec[i].first;
}
else if (vec[i].second == -1) {
if (vec[i].first == last) {
vector<stackItem> vec_tmp;
stackItem tmp = st.top(); st.pop();
if (tmp.state != -1) tmp.state = 1;
st.push(tmp);
st.push(stackItem(vec[i].first, 0));
}
else {
stackItem tmp = st.top(); st.pop();
tmp.state = -1;
st.push(tmp);
st.push(stackItem(vec[i].first, 0));
last = vec[i].first;
}
}
else if (vec[i].second == 1) {
stackItem tmp = st.top(); st.pop();
if (tmp.state == 1 && last == vec[i].first)
ans += 2;
else
ans++;
last = vec[i].first;
}
}
cout << ans + 1 << "\n";
}'알고리즘 > [C++]BOJ' 카테고리의 다른 글
| [백준BOJ] 2188 축사 배정 (0) | 2019.10.13 |
|---|---|
| [백준BOJ] 3078 좋은 친구 (2) | 2019.10.10 |
| [BOJ백준] 2170 선 긋기 (0) | 2019.10.10 |
