BOJ 24697 Interesting Subsegments

먼저, 배열이 주어졌을 때 합이 3의 배수인 부분 배열의 개수를 구하는 방법을 생각해 봅시다.

그 배열의 누적 합을 생각해 보면, 서로 다른 두 곳의 누적합의 차이가 3의 배수이면 그 두 곳을 양 끝점으로 하는 부분 배열의 합은 3의 배수입니다. 따라서, 누적합 값들 중에서 3으로 나눈 나머지가 $i$인 것의 개수를 $a_i$라고 하면, 합이 3의 배수인 부분 배열의 개수는 $\frac{a_0 (a_0+1)}{2} + \frac{a_1 (a_1-1)}{2} + \frac{a_2 (a_2-1)}{2}$와 같습니다. (0의 경우 원소 0개를 포함한 누적합도 선택 가능합니다.)

또한 $n = a_0 + a_1 + a_2$도 성립하므로, $k = \frac{a_0 (a_0+1)}{2} + \frac{a_1 (a_1-1)}{2} + \frac{a_2 (a_2-1)}{2}$에 $a_2 = n - a_0 - a_1$을 대입하여 $a_0$과 $a_1$에 대한 이차방정식을 얻을 수 있습니다.

이제 $a_0, a_1, a_2$가 정해졌을 때 사전 순으로 최소인 배열을 구하는 방법을 생각해 봅시다.

사전 순으로 최소이려면 일단 맨 앞에 0이 가능한 한 많아야 합니다. 0개의 합도 0이므로, $a_0$개의 0을 맨 앞에 몰아서 배치해 줍니다. 그 다음에는 0이 올 수 없으므로 1이나 2가 와야 하는데, $a_1$이 0이 아니라면 1이 먼저 오는 것이 이득입니다. 이제 누적합이 서로 같은 값이 오면 원래의 배열에는 0이 적히게 되므로, 남은 1을 모두 연달아서 배치합니다.

이제 서로 다른 $a_0, a_1, a_2$들 중에서 최적을 고르려면 $a_0$이 가능한 한 많은 것, 그 중에서는 $a_1$이 가능한 한 많은 것을 골라야 함을 알 수 있습니다.

일단 $a_0$이 가능한 한 커야 하므로, $a_0$을 큰 것부터 고정해 봅니다. 그러면 앞에서 얻은 이차방정식을 풀어 볼 수 있습니다. 그 결과에 문제가 없으면 ($a_0, a_1, a_2$ 모두 음이 아닌 정수) 그 중에서 $a_1$이 큰 것에 해당하는 배열을 출력하면 됩니다.