[BOJ 8230] Squarks

스쿼크의 질량을 오름차순으로 정렬한것을 \((x_1, x_2, x_3, \cdots, x_n)\), \((x_i + x_j)\)들의 집합을 오름차순으로 나열한것을 \((a_1, a_2, a_3, \cdots, a_{\frac{n(n-1)}{2}})\)이라고 하자. 현재 알 수 있는 사실은 \(x_1 + x_2=a_1\), \(x_1 + x_3 = a_2\)이라는 것이다. \(a_3\)부터는 \(x_2 + x_3\)과 \(x_1 + x_4\)의 대소비교를 할 수 없기 때문에 얻을 수 있는 정보가 없다.

당장 할 수 있는게 딱히 없으므로 얻을 수 있는 정보를 늘리기 위해서 임의로 값을 지정해보도록 하자. 만약 임의의 \(k ( 3 \le k )\)에 대해서 \(x_2 + x_3 = a_k\)라고 가정해보자. 그럼 무슨 일이 일어나냐면, \((x_1 + x_2)\), \((x_1 + x_3)\), \((x_2 + x_3)\)의 값을 모두 알고 있으므로 \(x_1\), \(x_2\), \(x_3\)의 값을 결정할 수 있다는 것과, 현재 어떤 두 수의 합으로 결정되는지 정해지지 않은 \(a_i\)들 중에 가장 작은 수는 \(x_1 + x_4\)라는 것으로부터 \(x_4\)의 값도 정해진다는 것이다.

사실 잘 생각해보면 \(x_4\)의 값이 정해지는것으로 끝나는것이 아니다. 우리가 만약 \(x_1, x_2, \cdots, x_i\)까지의 값을 모두 알고 있다고 가정해보자. 그렇다면 \(x_1\)부터 \(x_i\)까지의 수들중 임의의 두 수의 합으로 구해지지 않는 \(a_i\)중 가장 작은 수는 무조건 \(x_1 + x_{i+1}\)이라는 사실을 알 수 있다. 즉, 연쇄적으로 모든 \(x_i\)의 값들을 결정해 줄 수 있다. \(x_i\)의 값들이 결정됨에 따라 \(a_i\)의 값들도 정해지므로, 만일 \(a_i\)들을 구성하는 과정에서 모순이 발생한다면 이는 \(x_2 + x_3 = a_k\)임을 가정했을때 이것이 틀렸다는 사실을 의미하고, 모순이 발생하지 않는다면 해당 집합이 답의 경우 중 하나가 된다.

가능한 \((x_2 + x_3)\)의 후보는 \((x_2 + x_3)\)보다 작아질 수 있는 집합이 \((x_1 + x_i)\)밖에 없으므로 \(a_1, a_2, \cdots, a_n\)으로 \(n\)개이고, 각 후보에 대해서 모순이 일어나는지 확인할 때 \(\frac{n(n-1)}{2}\)개의 수에 대해서 multiset, map등의 자료구조를 사용하여 모순을 체크해야 하므로 시간복잡도는 대략 \(O(n^3\log{n^2})\)정도로 해결할 수 있다.