공연장 (seat) 대회 풀이

대회 풀이

이 문제는 시작 줄과 끝 줄의 반지름을 나타내는 D1과 D2가 주어지고 각 줄에는 반지름만 큼의 관중석이 북쪽부터 같은 간격으로 있을 때, 무대의 중심이 앞의 관중석에 가려지지 않고 보이는 관중석의 개수를 구하는 문제이다.
이는 모든 관중석의 각도를 구해 각도가 같은 관중석을 1개만 제외하고 지우는 방법으로 해결할 수 있다. i번째 줄의 j번째 관중석의 각도는 360 × j ÷ i 이며 모든 관중석에 대해서 360은 공통되므로 관중석의 각도를 j ÷ i를 이용해 비교할 수 있다. 중복되는 관중석을 효율 적으로 제거하기 위해서 이를 기약분수로 만든 후 정렬하여 서로 다른 각도 값의 수를 세면 답을 구할 수 있다.
g가 i,j 의 최대공약수이면 j/g / i/g 이 j/i 의 기약분수가 된다. 두 수의 최대공약수는 유클리드 호제법을 이용해 쉽게 구할 수 있다. 모든 관중석 (i,j)에 대해 (i/g , j/g)를 크기 순서대로 정렬하면 O(N^2 log N)의 시간 복잡도로 답을 구할 수 있다.
1번 부분 문제는 D1 = D2인 경우로 모든 관중석이 보이므로, D1을 그대로 출력하면 된다.
2번과 3번 부분문제는 모든 줄의 쌍 K, L에 대해서 각 줄의 모든 관중석 쌍의 각도를 비교 해 가리는 관중석을 제거하여 O(N^4)�에 답을 구할 수 있다.
4번 부분문제는 모든 줄의 쌍 K, L의 두 관중석의 각도를 비교할 때 각도 순서대로 하나씩 만 비교하면 O(N)에 중복되는 관중석을 모두 확인할 수 있고,O(N^3)으로 답을 구할 수 있 다.
   

[홈으로] [뒤 로]