[백준] 31408 - 당직 근무표

[문제]

---

https://www.acmicpc.net/problem/31408

[풀이]

---

당직 근무를 개선할 수 없는 상황은 한 사람이 2일 연속으로 서는 경우이다.

1. N이 짝수일 때, N=2k 라고 하고 k개의 상자 안에 병사를 2명 씩 배정한다고 하자.
   한 병사가 k+1번 당직을 선다면, 비둘기 집의 원리에 의해 적어도 한 상자에는 같은 병사가 배정된다.
   즉, 한 병사는 일수 N 중에 k번까지 당직을 설 수 있다.
2. N이 홀 수 일 때, N=2k+1 이라 하고, k개의 상자 안에 병사를 2명 씩 배정한다고 하자.
   한 병사가 k+1번 당직을 선다면, 비둘기 집의 원리에 의해 적어도 한 상자에는 같은 병사가 배정된다.
   즉, 한 병사는 일수 N 중에 k+1번까지 당직을 설 수 있다.

위 두 사실을 종합하면, 한 병사는 일수 N 중 최대 $\frac{N+1}{2}$번 당직을 설 수 있다.

[코드]

---

n = int(input())
a = list(map(int,input().split()))

ai = dict()
mv=0
for e in a:
    if e in ai.keys():
        ai[e] += 1
    else:
        ai[e] = 1
    if ai[e] > mv:
        mv = ai[e]

if mv <= (n+1)//2:
    print("YES")
else:
    print("NO")