연속한 3명이 같은 색깔이 되어서는 안된다는 조건을 그대로 활용해서 답을 찾으려면 만만치 않다. twosat 으로 모델링하는것이 가능할지도 모르겠다.
조건을 조금 변형해서, 1번과 2번, 3번과 4번, 5번과 6번, .. 이런식의 페어들이 같은 색깔이 되지 않아야 된다고 모델링해보자.
이 조건은 연속한 3명이 같은 색깔이 되지 않는다는 원래 조건보다 더 타이트한 조건이다. 즉, 이 조건을 만족하는 답을 찾으면, 원래 조건도 만족한다.
이 조건을 만족하는 답을 찾는 것은 간단하다. 그래프를 만들고, 다른색이어야 하는 페어들에 대해서 엣지를 만든다. 문제에서 주어진 order들에 엣지를 만들고, 지금 말한대로 1-2, 3-4, …, 이런 엣지들을 추가한다. 이제 이 그래프를 2색 색칠하면 답을 찾을수 있다.
신경쓰이는 점은, 우리가 변형한 조건이 처음 조건보다 더 타이트한 조건이기 때문에, 원래 조건을 만족하는 답이 있음에도 불구하고 이 조건을 만족하는 답이 없는 경우가 있을 수 있지 않을까 하는 걱정이다. 그러나 조금 생각해보면, 이 조건을 만족하는 답이 항상 존재한다는 것을 알수 있다. 2색 색칠이 불가능하려면, 홀수 사이클을 포함하고 있어야 한다. order에서 추가된 엣지들은 모두 disjoint하고, 그 뒤에 인접한 애들간에 추가된 엣지들도 disjoint 하다. 따라서, 사이클이 생긴다면, order엣지와 인접엣지가 번갈아가면서 나오는 형태일수 밖에 없고, 그렇다면 사이클의 크기는 항상 짝수일수밖에 없다.
그래프에 엣지를 추가하는데에 O(V), 사이클 체크에 O(V+E)인데.. 이 문제에서는 E=O(V)이므로 총 시간복잡도는 O(V)