[ARC030 1] 閉路グラフ

난이도: 556

 

번역

정점이 \( n \) \( (n \ge 3) \)개인 사이클 그래프가 주어집니다.

사이클 그래프란, 본문의 사진과 같이 \( 1 \)번 정점과 \( 2 \)번 정점이 연결되어있고, \( 2 \)번 정점과 \( 3 \)번 정점이 연결되어있고, ..., \( n-1 \)번 정점과 \( n \)번 정점이 연결되어있고, \( n \)번 정점은 \( 1 \)번 정점과 연결되어있는 그래프를 의미합니다.

 

당신은 이 그래프에서 일부 정점을 지워서 \( k \)개의 연결 요소만을 남기고 싶어합니다.

정점을 지우게 되면, 그 정점에 연결되어있던 간선들도 같이 지워집니다.

원한다면, 아무 정점도 지우지 않는 것도 가능합니다.

이를 직접 해보기 전에, 정말 \( k \)개의 연결 요소만을 남길 수 있는지 판별해보세요.

 

태그

• Ad-Hoc (애드 혹)
• Mathematics (수학)

 

풀이

1. 연결 요소의 최대 개수는?

만약 정점이 짝수개였다면, 지우고 / 안 지우고 / 지우고 / 안 지우고 / ...를 반복해서 최대 \( \frac{n}{2} \)개의 연결 요소를 남길 수 있습니다.

홀수개였다면, 그렇게 지워서 \( \left\lfloor \frac{n}{2} \right\rfloor \)개의 연결 요소를 남길 수 있습니다.

 

2. 최댓값보다 더 적은 개수는?

\( k \)개가 만들 수 있는 최대 개수이고, 우리의 목표가 \( k' \)개라면, \( k' \)개 역시 항상 만들 수 있습니다.

방법은 간단한데, 우선 \( k \)개를 만든 뒤 \( k' \)개만 남기고 나머지는 지워버리면 됩니다.

 

코드

그러니, 문제의 답은 연결 요소의 최대 개수인 \( \left\lfloor \frac{n}{2} \right\rfloor \)과

우리의 목표치인 \( k \)를 비교하면 얻어낼 수 있습니다.

void Main(){
    int n, k; cin >> n >> k;
    if (n/2 >= k){ cout << "YES"; } else{ cout << "NO"; } cout << endl;
}