이중 루프를 사용해 밖 루프에서는 A-B 매칭 수, 안 루프에서는 A-C 매칭수를 루프 변수로 줍니다. 각각의 경우에 대해서 B-C 매칭 갯수는 min(n(B), n(C))가 최선이겠지요? 이런 방법으로 모든 A-B, A-C 매칭 경우에 대해서 최선의 경우를 찾아보면 됩니다.

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테이블을 이용하는 방법으로 이를 피할 수 있다.

동적계획법으로 해결할 수 있습니다.
먼저 각각의 5개 항목에 대해서 우리가 고를 최선의 값들은 분명 어딘가의 equipment가 가진 값이라는 사실에 주목해야 합니다.
그렇다면 굳이 한 번에 최선의 값을 조합하려고 애쓰기보단, 5개 항목에 대해서 가능한 모든 선택의 조합을 동적계획법을 통해서 탐사해보고, 그 중에서 그 합이 가장 커지는 경우를 선택하면 되지 않을까요?
다음과 같이 동적계획법 점화식을 정의하여 보겠습니다.
D(index, status, pickCount) = 각각 인자의 의미부터 살펴보자면, 현재 index 번 째 equipment에서 몇몇 항목들을 고를지 말 지 고민중이며(해당 항목들이 최대값인지는 고려하지 않고), status는 equipment의 1 ~ 5번째 항목 중 내가 이전 인덱스에서 처리하지 않아서 현재 고를 수 있는 항목의 상태를 표현한 5개짜리 비트의 비트마스크, pickCount는 내가 앞으로 한 항목이라도 참조할 equipment를 고를 수 있는 남은 횟수입니다. 이 때, 본 점화식은 index ~ N - 1번 equipment까지 살펴보면서 status에 표시된 항목들을 pickCount의 제한에 맞추어 살펴볼 때 취할 수 있는 항목들의 최대 합을 나타냅니다.
각각 항목의 범위는 0 <= index <= N - 1(zerobase), 0 <= status <= 2^5 - 1(5개 항목에 대한 비트마스크), 0 <= pickCount <= 5가 됩니다. 마지막 pickCount가 최대 5까지만 살펴봐도 되는 이유는, 5를 넘으면 모든 무기를 통털어서 각각의 항목에서 가장 뛰어난 값들을 하나씩 취하면 되는 걸 바로 알 수 있기 때문입니다.
위와 같이 점화식의 정의를 내렸을 때 D(index, status, pickCount)는 먼저 본 equipment를 전혀 참조하지 않을 경우인 D(index + 1, status, pickCount), 그리고 본 equipment를 하나라도 참조할 경우 중 가장 큰 값을 취하게 됩니다. 본 equipment의 항목을 하나 이상 참조하게 될 경우의 값들에 대한 의사코드는 다음과 같습니다.

for(int toChoose = 1; toChoose < (1 << 5), toChoose++)
    if((status & toChoose) == toChoose)
    {
        int currentAnswer = D(index + 1, status ^ toChoose, pickCount - 1);
        for(int j = 0; j < 5; j++)
            if(toChoose & (1 << j)) currentAnswer += data[index][j];
        if(currentAnswer > D[index][status][pickCount]) D[index][status][pickCount] = currentAnswer;
    }

5개 항목을 고를 수 있는 31가지 경우 중 현재 상태에서 가능한 경우에 대해서, 현재 equipment에서 해당 값들을 취하고 남은 값의 계산은 다음 점화식에 넘겨 계산합니다.

작업 시간이 500밖에 되지 않기때문에 1 부터 500까지 모든 작업 시간에 대해서 순서대로 현재 할 수 있는 최선의 일을 인부들에게 배분해주면 해결할 수 있는 그리디 문제입니다. 시간 1에서부터 진행하며, 현재 시간 t에 대해서 시작시간이 t보다 빠르거나 같은 일감들 중 (데드라인 - 남은 일 시간)이 작은 순서대로 정렬하여 가장 앞 m개의 일을 인부들에게 나누어주어 일 량을 1씩 줄이면 됩니다.

단어 길이가 최대 15로 매우 짧기 때문에 모든 경우를 살펴보는 백트래킹으로도 충분히 해결이 가능합니다.

bool backtr(int i1, int i2)
{
    char ch = 현재 standard english 단어의 알파벳;
    if(ch가 백트래킹중 이전에 등장한 적이 없었다면)
        mapping[ch] = Leet.substr(i2, 1), Leet.substr(i2, 2), Leet.substr(i2, 3) 중 하나로 설정하고 각각의 경우에 대해서 backtr(i1 + 1, i2 + 1), backtr(i1 + 1, i2 + 2), backtr(i1 + 1, i2 + 3) 을 참조하여 해당 맵핑으로 오류없이 끝까지 탐색할 수 있는지를 확인한다.
    else
        string mapped = mapping[ch];
        if(Leet.substr(i2, mapped.size()) == mapped) // 이전에 맵핑해 둔 알파벳이 이번에도 들어맞는다면
            return backtr(i1 + 1, i2 + mapped.size());
        else return false;
}

대략 위와 같은 형태로 처음 만나는 알파벳이라면 길이 1 ~ 3중에서 한 종류를 맵핑해서 탐색을 계속 해 보고, 이전 탐색중에 나왔던 값이라면 이번에도 해당 값으로 탐색을 끝까지 진행할 수 있는지 살펴보아 해결할 수 있습니다.

최대한 일감들의 덩어리를 적게 만드는게 목표인데요. 문제의 조건 중 시작 시간이 나보다 같거나 느린 일은 데드라인도 반드시 같거나 늦다는 제한 조건이 있습니다. 이 조건때문에 주어진 모든 일들을 시작 시간에 따라서 정렬한 뒤(시작 시간이 같다면 데드라인이 빠른 순으로 정렬) 데이터를 앞에서부터 살펴보며 문제를 해결할 수 있습니다.
제일 먼저 가장 첫 데이터는 해당 일의 가장 뒷 데드라인에 배치합니다. 두 번째 일은 데드라인이 첫 번째 일보다 적어도 앞쪽은 아니기 때문에 첫 번쨰 일의 마지막 시간 + 1에 배치하거나, 첫 번째 일을 한 번 앞으로 밀면 배치할 수 있습니다. 세 번째 일도 마찬가지로 가장 뒤에 붙이거나 앞에 처리된 일들을 한 칸 앞으로 밀어가면서 붙일 수 있는데요. 이와 같이 앞으로 일들을 밀다 보면 언젠가는 어떤 일이 자신의 시작 시간까지 도달하여 더 이상 앞으로 밀려날 수 없는 상태에서 그 다음 일이 해당 일을 앞으로 밀려는 상황이 발생할 수 있습니다. 그러면 그 때까지 처리된 모든 일들을 한 덩어리로 가정하고, 현재 처리해야 하는 그 다음 일은 새로운 덩어리의 시작으로 삼아야 합니다. 가장 첫 데이터와 마찬가지로 해당 일의 데드라인까지 일을 밀어두고, 그 다음 일부터 뒤에서 하나씩 붙여나가시면 됩니다.
위와 같이 최대한 일들을 많이 붙여나간 뒤에, 모든 일 배치가 끝나면 지금까지 만들어졌던 일 덩어리의 갯수를 출력하시면 됩니다.

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) 이들은 O(N^2)에 구할 수 있다.
2. 답은 nC3 - sum(a(i)*b(i))/2가 된다. 이는 세 변의 색이 모두 같은 삼각형을 제외한 나머지 삼각형에서는 정점에 연결되어 있는 변의 색이 다른 점이 두개, 같은 점이 한개가 나오기 때문이다. 이를 계산하는데 O(N)의 시간이 걸린다.