PS 이야기

이 문제에서 독특한 성질의 그래프가 주어진다. 답으로 어떤 노드 집합을 구해야하는데, 이 노드 집합에 있는 각 노드는 서로 연결되어 있지 않으며, 각 노드별로 주어진 특성값의 합이 최대가 되어야한다. 아직 이 문제의 정해를 찾지 못 했다. 우선 69점 받는 방법을 설명하겠다. 부분 문제1) 노드가 많아야 10개이므로 각 노드에 대해서 집합에 포함되는지 포함되지 않는지 구하는 경우의 수는 노드의 개수가 $n$개라 할 때, $2^n$개이다. $2^n$가지에 대해 모두 가능한 집합인지 확인하고, 최대값을 갱신하면 된다. 부분 문제2) 입력으로 주어지는 그래프에 간선이 존재하지 않는다. 따라서, 모든 노드의 값을 더해주면 된다. 부분 문제3) 입력으로 주어지는 그래프는 완전그래프다. 따라서, 노드의 값들 중 최..