1. 목적 함수 : Sum { Length(color) }
2. Length(c) = LastIdx(c) - FirstIdx(c) + 1 이므로 결국, Sum { LastIdx } + Sum { -FirstIdx }를 최소화 시키는 문제로 볼 수 있다.
3. 2개의 차 행렬은 앞에서부터 순차적으로 합쳐지기 때문에 첫 번째 차 행렬에서 i개의 차량이 합쳐지고, 두 번째 차 행렬에서 j개의 차량이 합쳐졌을 때를 상태 공간으로 삼아 동적계획법을 수행할 수 있다.
4. 이를 D[i][j]라고 하자. 임의의 [i x j]에 대해 그 다음 차량을 합칠때 그 차량 색깔이 처음으로 등장하는지/마지막으로 등장하는 지 여부를 알 수 있으므로 2번의 목적 함수를 계산할 수 있다.
5. 시간 복잡도는 O(N^2).
6. N^2크기의 DP테이블을 잡으면 메모리 제한에 걸리지만 D[i][j]는 항상 D[i-1][j] 또는 D[i][j-1]에서 영향을 받으므로 2*N크기만의 DP테이블을 이용하는 방법으로 이를 피할 수 있다.

1. 임의의 점을 중심으로 그보다 인덱스가 작은 점을 잇는 선분과 인덱스가 큰 점을 잇는 선분의 값이 같은 가짓수를 구한다. 이를 n(A)라 하자.
2. n(A)는 O(N^2)시간에 구할 수 있다. 임의의 점 i에 대해 x<i 이면서 E[x][i] = 0 인 x의 갯수를 구하고, i<y 이면서 E[y][i] = 0인 y의 갯수를 구해서 이를 곱하여 더하는 식으로 반복한다.
3. 임의의 i<j<k 에 대해 E[i][j]!=E[i][k]인 (i,j,k)의 가짓수를 O(N^2)에 찾을 수 있다. 이를 n(B)라 하자.
4. (3에 대한 방법 설명) : 각 i에 대해 j보다 값이 크면서 E[i][k]=0인 k의 수를 p0(j)라고 하고 비슷한 방법으로 p1(j)를 정의한다.
5. p0(j) = p0(j+1) + 0 or 1 를 이용해서 j값이 1씩 변할때마다 O(1)시간에 p0,p1값을 구할 수 있다.
6. 마찬가지로 i>j>k에 대해 E[i][k]=E[i][j]인 (i,j,k)의 가짓수를 O(N^2)에 찾을 수 있다. 이를 n(C)라 하자.
7. 이때 우리가 원하는 답은 {n(A)-n(B)+n(C)}/2이다.
8. i<j<k가 있을때 {E[i][j],E[j][k],E[k][i]}의 가능한 조합은 {000,001,...111}이다. n(A)는 {000,001,110,111}에 해당된다. n(B)는 {001,011,100,110}, n(C)는 {000,011,100,111}에 해당된다. n(A)-n(B)+n(C)를 계산하면 오직 {000,111}에 관한 항만 남는다.

다른 방법

1. 각정점 i에 대해 a(i)와 b(i)를 계산한다. a(i)는 E[i][j]가 0인 개수, b(i)는 E[i][j]가 1인 개수이다. (i != j)
2. 답은 nC3 - sum(a(i)*b(i))/2가 된다. 이는 세 변의 색이 모두 같은 삼각형을 제외한 나머지 삼각형에서는 정점에 연결되어 있는 변의 색이 다른 점이 두개, 같은 점이 한개가 나오기 때문이다.