테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 당직 근무표 ======

===== 풀이 =====
  * ceil(N/2) 번 이상 당직을 서는 병사가 있으면, 이틀 연속으로 근무하는 것을 피할수 없다. 아무도 ceil(N/2) 번 이상 당직을 서지 않는다면, 아무도 이틀 연속 근무를 하지 않도록 배치가 가능하다.
  * 가장 근무일수가 많은 병사의 근무일수가 ceil(N/2) 이상인지 확인하면 끝. 시간복잡도는 O(n)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 31408. 당직 근무표".

- Problem link: https://www.acmicpc.net/problem/31408
- Solution link: http://www.teferi.net/ps/problems/boj/31408
"""

import collections


def main():
    N = int(input())
    a = input().split()

    is_possible = max(collections.Counter(a).values()) <= (N + 1) // 2
    print('YES' if is_possible else 'NO')


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:브론즈_1}}