문제 바로가기
문제:
이하는 최근 사과나무 씨앗을 구매하여 농장 뒷뜰에 일렬로 $1$번부터 $N$번까지 심었다. 이 나무들의 초기 높이는 모두 $0$이다. 사과나무를 무럭무럭 키우기 위해 이하는 물뿌리개 $2$개를 준비했다. 한 물뿌리개는 나무 하나를 $1$만큼 성장시키고, 다른 물뿌리개는 나무 하나를 $2$만큼 성장시킨다. 이 물뿌리개들은 동시에 사용해야 하며, 물뿌리개를 나무가 없는 토양에 사용할 수는 없다. 두 물뿌리개를 한 나무에 사용하여 $3$만큼 키울 수도 있다. 물뿌리개 관리 시스템을 전부 프로그래밍한 이하는 이제 사과나무를 키워보려고 했다. 그 순간, 갊자가 놀러와서 각 사과나무의 높이가 이런 배치가 되었으면 좋겠다고 말했다. 이제 이하는 약간 걱정이 되기 시작했는데, 갊자가 알려준 사과나무의 배치를 이 프로그램 상으로 만들어내지 못할 수도 있기 때문이다. 이하는 이제 프로그램을 다시 수정하느라 바쁘기 때문에, 두 물뿌리개를 이용해 갊자가 알려준 사과나무의 배치를 만들 수 있는지의 여부를 판단하는 과정은 여러분의 몫이 되었다.
입력:
첫 번째 줄에는 자연수 N이 주어진다. ( 1 \leq N \leq 100\ 000$) 이는 이하가 뒷뜰에 심은 사과나무의 개수를 뜻한다. 두 번째 줄에는 N개의 정수 h_1,h_2,\cdots,h_N이 공백으로 구분되어 주어진다. ( 0 \leq h_i \leq 10\ 000) h_i는 갊자가 바라는 i번째 나무의 높이이다.
출력:
첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다.
풀이:
import sys
n = int(input())
lst = sorted(list(map(int, sys.stdin.readline().rstrip().split(" "))), reverse=True)
count = sum(lst) // 3
if sum(lst) % 3 != 0:
print("NO")
else:
for a in lst:
count -= a//2
if count > 0:
print("NO")
else:
print("YES")
리스트에 있는 숫자의 합이 3으로 나눴을때 합이 0 이 아니면 나올 수 없다. -> "NO"
그게 아닐 경우에는 1과 2를 이용해서 lst를 만들어야한다.
2만큼 성장시키는 물뿌리개를 사용한 횟수가, 나무가 걸리는데 걸리는 총 일수 보다 커야지 다 키울 수 있다.
예를들어 1 3 1 3 1 이면 >> 3일이 걸린다.
물뿌리개 2를 사용할 수 있는 횟수가 총 성장 일수보다 작다는 것은 1을 더 많이 사용해야 하는 것이라서 정답이 될 수가 없다.
댓글