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()
ps/problems/boj/19539.txt · 마지막으로 수정됨: 2022/01/27 01:50 저자 teferi
토론