dr3n20bub   9달 전

이 문제를 제가 이해를 잘 못 하고 있는건지 모르겠습니다.


아래의 예제 입력을 기준으로 보면,

5
97 31
1 45
27 5
11 65
43 72

[(97, 31) 기준]   (27, 5), (43, 72)와 교차하지 않음 -> 교차하지 않는 원의 현들의 개수 : 3 (기준이 되는 현 포함)

[(01, 45) 기준]   (27, 5)와 교차하지 않음 -> 교차하지 않는 원의 현들의 개수 : 2 (기준이 되는 현 포함)

[(27, 05) 기준]   (97, 31), (01, 45), (43, 72)와 교차하지 않음 -> 교차하지 않는 원의 현들의 개수 : 4 (기준이 되는 현 포함)

...


이렇게 직접 구해보면 (27, 05) 기준에서 교차하지 않는 원의 현들의 개수가 4가 나오므로, 최대 개수는 4가 출력되어야 하는 것 아닌가요?

혹시 기준이 되는 현(자기 자신)을 포함하지 않아야 하는 것이 아닌지에 대해서도 생각해보았으나,

문제에서 '서로' 교차하지 않는 현들의 최대 개수를 출력하라했고

N=1일 경우, 서로 교차하지 않는 현들의 최대 개수인 1이 출력되어야 하므로

기준이 되는 현(자기 자신)이 포함되어야 한다고 생각했습니다.


일단 알고리즘은 짜놓았는데, 예제 입력과 예제 출력을 보니 제가 생각하는 출력과 맞지 않는 것 같아 여쭤봅니다.

제가 문제를 잘 못 이해했나요?

ntopia   9달 전

선택한 현들 끼리는 전부 서로 교차하지 않아야 합니다

ntopia   9달 전

[(27, 05),  (97, 31), (01, 45), (43, 72)]

이렇게 4개를 골라버리면

(01,45) 가 다른것과 교차하게 되니 조건에 맞게 고른 것이 아니죠

dr3n20bub   9달 전

아 그렇군요.

그렇다면 {(27, 05), (97, 31), (43, 72)}인 경우가 '교차하지 않는 원의 현들의 최대 집합'이 되는 것이네요. 감사합니다.

댓글을 작성하려면 로그인해야 합니다.