[Codeforces] Codeforces Round #780 (Div. 3) - B

Problem

 

B. Vlad and Candies

Problem

 

https://codeforces.com/problemset/problem/1660/B

Problem - 1660B - Codeforces

 얼마 전에, Vlad는 생일 선물로 사탕 꾸러미를 받았다. 거기에는 n 종류의 사탕이 있으며, i 종류의 사탕이 $a_i$개씩 들어 있다. ($1 \le i \le n$).

 

 Vlad는 매일 정확히 하나의 사탕을 먹기로 하였으며, 현재 가장 많이 남아 있는 종류의 사탕 중 하나를 고르기로 하였다(만약 그러한 종류가 여러 개라면 그중 아무거나 고른다). 최대한의 먹는 기쁨을 누리기 위해, Vlad는 연속해서 같은 종류의 사탕을 먹지 않기를 원한다.

 

 그를 도와 그가 연속해서 같은 종류의 사탕을 먹지 않고 모든 사탕을 먹을 수 있는 알아보자.

 

 

Input

 첫째 줄에는 테스트 케이스의 수를 나타내는 하나의 정수 t($1 \le wet \le 10^4$)가 주어진다.

 

 다음으로 t개의 테스트 케이스에 대한 정보가 각각 2줄로 주어진다.

 

 테스트 케이스의 첫번째 줄에는 꾸러미에 들어 있는 사탕의 종류의 수를 나타내는 하나의 정수 n($1 \le n \le 2 \cdot 10^5$) 이 주어진다.

 

 테스트 케이스의 두번째 줄에는 i종류의 사탕의 개수를 나타내는 n개의 정수 $a_i(1 \le a_i \le 10^9)$가 주어진다.

 

 모든 테스트 케이스에 대하여 n의 합은 $2 \cdot 10^5$이 넘지 않음이 보장된다.

 

 

Output

 t개의 줄에 걸쳐, 입력으로 주어진 테스트 케이스에 대한 답을 출력하여라. 답은 Vlad가 계획대로 사탕을 먹을 수 있으면 "YES"를, 그렇지 않으면 "NO"로 출력한다.

 

 

Example

input	output
6 2 2 3 1 2 5 1 6 2 4 3 4 2 2 2 1 3 1 1000000000 999999999 1 1	YES NO NO YES YES YES

 

 

Note

 첫번째 예제에서, 다음과 같이 먹어야 한다.

• type 2, 가장 많이 남아 있기 때문. 현재 a = [2, 2];
• type 1, type 2와 사탕의 수는 같지만, 하나는 바로 직전에 먹었기 때문. 현재 a = [1, 2];
• type 2, 가장 많이 남아 있기 때문. 현재 a = [1, 1];
• type 1. 현재 a = [0, 1];
• type 2. 현재 a = [0, 0];

 

 두번째 예제에서, 모든 사탕의 종류가 같다. 따라서 연속해서 다른 종류의 사탕을 먹는 것은 불가능하다.

 

 세번째 예제에서, 가장 많이 남아 있는 종류의 사탕이 type 2이며, 다음으로도 type 2이다.

 

 

Tutorial

 가장 많이 남아 있는 사탕을 우선으로 먹어야 하며, 다음으로는 연속해서 같은 종류의 사탕을 먹으면 안 된다. 이 두 조건을 만족시키는지를 보기 위해서는 가장 많은 두 종류의 사탕만 보면 된다. 이 두 종류의 사탕의 차이가 1 이하이면 가능하고 그렇지 않으면 불가능하다.

 

 우선 가장 많은 종류의 사탕이 다음으로 많은 종류의 사탕보다 2개 이상 많게 되면 가장 많은 종류의 사탕을 연속해서 2개 이상 먹어야 하기 때문에 불가능하다. 만약 가장 많은 종류의 사탕이 여러 개라면 우리는 이들을 차례로 하나씩 먹으며 모든 사탕을 먹을 수 있다. (가장 많은 종류의 사탕이 다음으로 많은 종류의 사탕보다 1개 더 많다면, 가장 많은 종류의 사탕을 먹고 나면 가장 많은 종류의 사탕이 여러 개가 되며, 계획대로 먹을 수 있게 된다.)

 

 요약

• 가장 많은 종류의 사탕과 다음으로 많은 종류의 사탕의 차가 1 이하이면, YES
• 그렇지 않으면, NO

 

 

Solution

#include <bits/stdc++.h>

using namespace std;

int a[200010];

int main()
{
	int t, n, i;
	
	cin >> t;
	while(t--){
		cin >> n;
		for(i=0; i<n; i++) cin >> a[i];
		
		sort(a, a+n);
		
		if(a[n-1] - a[n-2] <= 1) cout << "YES\n";
		else cout << "NO\n";
	}
	
	return 0;
}

 

 

마치며...

 문제 해석 부분에서 살짝 시간이 걸렸다. 문제 본문을 보면 "choosing any of the candies of a type that is currently the most frequent"라는 부분이 있다. 나는 여기서 "현재 가장 자주 먹은 종류의 사탕을 고른다"라고 해석하였는데, 그렇게 되면 문제를 풀 수가 없게 된다. 사실 이 문장을 보자마자 n이 1일 때만 가능하겠구나라고 생각했지만 문제의 의도는 그게 아니었다. "자주 먹은"이 아니라 "남아 있는"이 문제의 의도였기 때문이다. 이번 문제를 풀며 영어의 중요성을 다시 한 번 느끼게 되었다.