[도움요청] FORTRESS 문제 예외 케이스가 무엇이 있을까요? realmind 질문에 포함되어야 할 내용 FORTRESS 문제를 풀던 중 아래와 같이 테스트했는데, 어디서 잘못된 것인지 잘 모르겠습니다. 문제는 아래와 같은 답일 것이라고 생각하고 풀었는데요. (tree의 높이) 이거나 (가장 긴 2개 subtree의 높이합) 높이는 height()에서 구하고 longest는 child가 있을 때, 가장 큰 두 subtree의 높이합으로 height()에서 longest 전역변수에 값을 바로 업데이트 합니다. #include <iostream> #include <vector> #include <algorithm> #define MAX_C (100) #define MAX_N (100) using namespace std; struct Tree { int r, x, y; vector<Tree*> children; bool operator <(const Tree &rside) const { return (r < rside.r); } }; Tree trees[MAX_N]; int longest = 0; bool enclose(int out, int in) { int x = trees[out].x - trees[in].x; int y = trees[out].y - trees[in].y; int r = trees[out].r - trees[in].r; return ((trees[out].r > trees[in].r) && (x*x + y*y < r*r)); } Tree *makeTree(int n) { for(int i = 0; i < n; ++i) { for(int j = i + 1; j < n; ++j) { if(enclose(j, i)) { trees[j].children.push_back(&trees[i]); break; } } } return &trees[n-1]; } int height(Tree *root) { int h1 = -1, h2 = -1; for(Tree *child : root->children) { int ch = height(child); if(ch >= h1) { h2 = h1; h1 = ch; } } if(h2 >= 0) { longest = max(longest, h1 + h2 + 2); } return (h1 + 1); } int main(void) { int nTests, n; cin >> nTests; while(nTests--) { cin >> n; for(int i = 0; i < n; ++i) { cin >> trees[i].x >> trees[i].y >> trees[i].r; trees[i].children.clear(); } sort(trees, trees + n); Tree *root = makeTree(n); longest = -1; int h = height(root); cout << max(h, longest) << endl; } return 0; } 제가 놓치고 있는 예외케이스가 있을 것으로 판단되는데요. 어떤 예외케이스가 있을까요? 9년 전
2개의 댓글이 있습니다. astein 케이스의 문제가 아니라, 구현상의 문제로 보입니다 int height(Tree *root) 구현에서 트리의 차일드가 3 이상일때 문제가 발생할 수 있습니다. 9년 전 link realmind astein 님 좋은 조언 감사합니다 :) 괜히 이상한 최적화를 하려고 하다가 문제가 발생했네요. 9년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
realmind
질문에 포함되어야 할 내용
FORTRESS 문제를 풀던 중 아래와 같이 테스트했는데, 어디서 잘못된 것인지 잘 모르겠습니다.
문제는 아래와 같은 답일 것이라고 생각하고 풀었는데요.
(tree의 높이) 이거나 (가장 긴 2개 subtree의 높이합)
높이는 height()에서 구하고 longest는 child가 있을 때, 가장 큰 두 subtree의 높이합으로 height()에서 longest 전역변수에 값을 바로 업데이트 합니다.
제가 놓치고 있는 예외케이스가 있을 것으로 판단되는데요.
어떤 예외케이스가 있을까요?
9년 전