djm03178   1년 전

지문이 너무 길고 중요 정보들이 눈에 띄지 않게 자연스럽게 끼어있어 주요 사항들을 정리해봅니다. 문제의 단순화 과정이 약간 섞여있습니다.

  • 문제에서 말하는 n개의 design을 정점, m개의 boat를 양방향 간선으로 생각할 수 있습니다.
  • 그래프를 그대로 놔두면, 연결된 간선이 하나뿐인 정점들과, 그 정점에 연결된 유일한 간선이 사라집니다. 이로 인해 다시 간선이 하나만 남게 된 정점이 생기면 연쇄적으로 그 정점과 간선이 사라집니다.
  • 하나의 연결 컴포넌트로 이루어진 그래프가 주어집니다. 이 그래프를 그대로 놔둘 경우 최소 하나의 정점은 마지막까지 사라지지 않음이 보장됩니다.
  • 여기에 k개의 "여분 boat"를 사용하여 사라지는 정점의 수를 최소화해야 합니다. 이 k개의 "여분 boat"는 처음에 주어지는 m개의 boat와는 달리 양방향으로 두 정점을 연결하지 않고 하나의 정점에만 연결되어 그 정점에 연결된 간선의 수를 하나 늘려주는 역할만 합니다.

댓글을 작성하려면 로그인해야 합니다.