백준 2533

2533번: 사회망 서비스(SNS)

 

  얼리어답터란 말이 기니 얼리어답터를 색칠된 노드로 생각한다. 처음엔 색칠된 노드의 이웃 노드는 색칠될 필요가 없으니 첫 노드를 색칠하고 그 다음 노드는 색칠하지 않고 그 색칠되지 않은 노드의 다음은 또 색칠하는 식으로 하면 최적의 경우가 나올 거라 생각했는데, 틀렸다. 색칠된 노드의 이웃 노드가 반드시 색칠되지 않을 필요는 없는데, 내 코드는 반드시 색칠되지 않은 노드여야 된다는 논리를 가지니 여기에 문제가 있을 게 뻔하다 생각했고 고치니 맞았다. 그런데 처음의 그 논리가 왜 틀렸는지 반례를 제시하지 못해서 계속 끙끙거렸는데, 드디어 반례를 생각해냈다 ㅠㅠ 

 

 

  번갈아서 색칠하면 홀수 번째, 또는 짝수 번째만 색칠되는데 각각 4, 3으로 최적이 아니다. 색칠된 노드의 경우 이웃 노드가 색칠된 노드일 때 아닐 때 모두 고려해서 최솟값을 받아야 한다.

 

 

 - Source code link

github.com/Bibidi/Algorithms/blob/master/boj/boj%202533.cpp