[백준_1953_사과나무] 골드5 python

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

19539번: 사과나무

• [백준_1953_사과나무] 골드 5
  • 수학, greedy 기법으로 푸는 문제이다
  • 목표로 하는 사과나무의 높이가 주어지는데 1,2의 성장세가 주어지는 성장 약으로 이 높이를 해당 조건에 충족할 수 있는지 묻는 문제이다.
  • x : 우선 사과나무의 높이의 총합이 3으로 나누어져야 물이 동시에 주어지기 때문에 성장 속도가 1과 2가 되는 물을 주는 물뿌리개의 조건에 부합할 수 있다.
  • 그러고 나서가 조금 까다로울 수 있는데, 목표로 하는 나무 높이들의 총합에 3으로 나눈 몫보다 반례: (1) 1 2 1 2 3 3 3 3 , (2) 1 2 1 2 6 6 6두 번째 반례를 보면 x의 조건을 충족시키고, 2의 몫개수의 합이 3의 몫 갯수의 합보다 작으면 안 됨을 알 수 있다.
  • 첫 번째 반례를 보면 x의 조건을 충족시키고 , 2의 몫 개수의 합은 곧 3의 몫갯수의 합이라고 볼 수 있다
  • arr 배열의 값들을 2로 나눈 몫들의 합이 같거나 커야 한다.

 

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

a,b = divmod(sum(arr),3)    #3으로 나눈 몫과 나머지

if not b :
    cnt = 0
    for i in arr:
        cnt += i//2
    if cnt >= a:
        print("YES")
    else:
        print("NO")
else:
    print("NO")