사용자 도구

사이트 도구


ps:problems:boj:31408

당직 근무표

ps
링크acmicpc.net/…
출처BOJ
문제 번호31408
문제명당직 근무표
레벨브론즈 1
시간복잡도O(n)
인풋사이즈n<=100,000
사용한 언어Python 3.11
제출기록40428KB / 84ms
최고기록84ms
해결날짜2024/02/19
출처

제3회 보라매컵 본선 Open Contest - A

풀이

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

코드

"""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()

토론

댓글을 입력하세요:
Q N Q J E
 
ps/problems/boj/31408.txt · 마지막으로 수정됨: 2024/03/05 15:04 저자 teferi