이 문제에서는 원의 가장자리에 배치된 n개의 상자가 주어지고, 두 개의 정수 a와 b로 구성된 Q개의 쿼리가 제공됩니다. 우리의 과제는 각 쿼리에 대해 원 위의 상자들을 서로 연결할 수 있는지 확인하는 프로그램을 작성하는 것입니다.
문제 설명
각 쿼리를 처리할 때, 이전 쿼리에서 이미 연결된 막대들의 교차 상태를 방해하지 않으면서 상자 a와 상자 b를 막대로 연결할 수 있는지 판단해야 합니다. 조건을 만족하면 possible(가능), 만족하지 않으면 not possible(불가능)을 출력합니다.
예시로 문제 이해하기
입력
n = 6
Q = 3
Queries = {{1, 3}, {2, 5}, {4, 5}}
출력
Possible Not possible Possible
설명
실선으로 표시된 막대는 서로 교차하지 않고 연결할 수 있는 경우이며, 점선으로 표시된 선은 기존 막대와 교차하여 연결할 수 없는 경우입니다.
해결 접근 방식
이 문제의 가장 단순한 해결 방법은 각 쿼리마다 주어진 상자 a와 상자 b를 연결할 수 있는지 직접 확인하는 것입니다. 이를 위해 바로 이전 쿼리의 값을 기준점(reference point)으로 저장해 두었다가, 새로운 연결이 가능한지 검사합니다.
쿼리 (i-1)의 상자 a와 b를 각각 기준점 ref1과 ref2라고 가정해 보겠습니다. 그다음 현재 쿼리의 두 점 a와 b가 기존 막대를 기준으로 서로 반대편에 위치하는지 확인하면 됩니다.
이를 위해 다음 두 가지 조건을 검사합니다.
조건 1 − (ref1 < a < ref2 이면서 ref2 < b < n)인 경우
조건 2 − (ref1 < b < ref2 이면서 ref2 < a < n)인 경우
두 조건 중 하나라도 해당되면 두 상자를 잇는 막대가 기존 막대와 교차하게 되므로, 결과는 not possible(불가능)이 됩니다.
구현 예제
아래는 위 접근 방식의 동작을 보여주는 C++ 프로그램입니다.
#include <iostream>
using namespace std;
int printSolutoin(int n, int a, int b, int ref1, int ref2, int lastConn){
if(lastConn == 0 && a != b)
return 1;
int temp;
if(a > b){
temp = a;
a = b;
b = temp;
}
if(ref1 > ref2){
temp = ref1;
ref1 = ref2;
ref2 = temp;
}
if( ( ref1 < a && a < b && b < ref2) )
return 1;
if( (ref1 <= a <= ref2) && (ref2 <= b <= n) ) return 0;
else if( (ref1 <= b <= ref2) && (ref2 <= a <= n) )
return 0;
return 0;
return 1;
}
void solveAllQueries(int n, int q, int query[][2]){
int lastConn = printSolutoin(n, query[0][0], query[0][1], 0, 0, 0);
lastConn?cout<<"Possible\n":cout<<"Not Possible\n";
for(int i = 1; i < q; i++){
lastConn = printSolutoin(n, query[i][0], query[i][1], query[i - 1][0], query[0][1], lastConn);
lastConn?cout<<"Possible\n":cout<<"Not Possible\n";
}
}
int main() {
int n = 6;
int Q = 3;
int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}};
solveAllQueries(n, Q, query);
return 0;
}
출력
Possible Not Possible Possible
첫 번째 쿼리 {1, 3}은 아직 연결된 막대가 없으므로 바로 연결이 가능하고, 두 번째 쿼리 {2, 5}는 첫 번째 막대와 교차하므로 불가능하며, 세 번째 쿼리 {4, 5}는 기존 막대와 겹치지 않아 연결이 가능합니다.