Sabor – Kattis, Kattis
A land far, far away has N Members of Parliament (MP). They had a turbulent and passionate debate on the law on amendments to the law on a new referendum on referendums. From Monday to Friday, all MPs joyfully came to work and argued all day. A diligent ne
open.kattis.com
문제를 다음과 같이 정리할 수 있다.
각 정점의 차수가 5 이하인 그래프가 주어질 때 모든 정점을 빨간색 또는 파란색으로 칠하려고 한다.
이때 각 정점에 대하여 자신과 동일한 색을 가진 이웃 정점의 수는 2개 이하여야 한다.
가능한 답 중 하나를 구하시오.
아무리 고민해도 모르겠어서 풀이를 봤다.
태그는 애드 혹이며 풀이는 의외로 간단하다.
각 정점에 임의의 색을 칠한 후 조건을 만족하지 않는 정점을 다른 색으로 칠하는 작업을 반복한다.
반복하다 보면 언젠가는 모든 정점이 조건을 만족하게 된다.
색이 동일한 두 정점을 연결하는 모든 간선의 수를 M이라고 하자.
어떠한 정점이 조건을 만족하지 않는다는 것은 해당 정점에 이러한 간선이 3개 이상 존재한다는 것이다.
해당 정점에 다른 색을 칠하게 되면 이러한 간선의 수는 2개 이하로 줄어든다.
따라서 반복할 때마다 M은 항상 감소하게 된다.
간선의 수는 최대 5/2N이므로 시간 내에 답을 구할 수 있다.
끝
'일기 (사실 근황임)' 카테고리의 다른 글
| 자격증 목록 (5) | 2022.10.29 |
|---|---|
| CP4 Chapter 1. Introduction (0) | 2022.10.28 |
| 부동 소수점 연산의 위험성 (0) | 2022.10.23 |
| BOJ 18789번 814 - 2 (2) | 2022.09.20 |
| 티스토리 모바일웹 비활성화 (최신 코드) (9) | 2022.09.19 |
