사용자 도구

사이트 도구


ps:problems:boj:19539

사과나무

ps
링크acmicpc.net/…
출처BOJ
문제 번호19539
문제명사과나무
레벨실버 1
분류

그리디

시간복잡도O(n)
인풋사이즈n<=100,000
사용한 언어Python
제출기록42028KB / 104ms
최고기록96ms
해결날짜2022/01/27

풀이

  • 우선 명확한 것. 나무의 높이의 합이 3의 배수가 아니면 불가능하다.
  • 나무의 높이의 합이 3의 배수일때도 1 1 1과 같은 경우에는 불가능하다. 4 1 1 와 같은 경우에는 가능하다
  • 나무의 높이의 합이 3n이라면, 2짜리 물뿌리개와 1짜리 물뿌리개를 각각 n번 뿌려야 할것이다. 물뿌리는 순서를 바꿔서 생각해서 2짜리 물뿌리개를 먼저 n번 뿌린 뒤에 1짜리 물뿌리개를 n번 뿌린다고 생각하자. 1짜리 물뿌리개를 못뿌리는 경우는 없으니, 처음에 2짜리 물뿌리개를 n번 뿌리는 것이 가능한지만 보면 된다. 2짜리 물뿌리개를 쓸수 있는 최대 횟수를 계산해서 그 값이 n이상인지 체크하면 된다.
  • 시간복잡도는 O(n)

코드

"""Solution code for "BOJ 19539. 사과나무".

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

Tags: [Greedy]
"""


def main():
    N = int(input())  # pylint: disable=unused-variable
    h = [int(x) for x in input().split()]

    q, r = divmod(sum(h), 3)
    print('YES' if r == 0 and sum(h_i // 2 for h_i in h) >= q else 'NO')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
D X S D C
 
ps/problems/boj/19539.txt · 마지막으로 수정됨: 2022/01/27 01:50 저자 teferi