[백준] 사과나무 : 19539번 - Python

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

19539번: 사과나무

 

 

 

문제의 접근 방법

 

- 두 물뿌리개는 반드시 동시에 사용해야 함.

1) 한 나무에 두 물뿌리개를 사용하는 방법 (3만큼 자람)

2) 각각 다른 나무에 사용하는 방법 (1만큼/2만큼 자람)

3) 나무가 없으면 물뿌리개를 사용할 수 없음 (0)

 

결론1 : 각 나무의 높이들을 더한 값이 무조건 3의 배수가 되어야 함!!! => 어떻게 물을 뿌리든 두 물뿌리개를 동시에 사용하기 때문에 한 번 물을 뿌릴 때마다 3씩 증가하기 때문이다.

나무가 자라나는 데 걸리는 총 일수 = 전체 나무의 높이들을 더한 값 / 3

 

결론2 : 2만큼 자라나는 물뿌리개를 사용할 수 있는 횟수가 총 일수보다 같거나 커야 함!!! => 결론1이 성립되었다는 가정하에 물뿌리개 1과 물뿌리개 2가 뿌려지는 횟수는 똑같이 증가하는데 2만큼 성장시켰다는 것은 나머지 나무들을 1만큼 성장시킬 수 있는 것이다. 따라서 2만큼 성장시킬 수 있는 것을 중심으로 계산해야 한다.

ex) 1 3 1 3 1

이 예시는 결론 1을 만족시키지만 2만큼 성장시키는 물뿌리개는 최대 2번까지 밖에 사용하지 못한다. 그렇게 되면 1만큼 성장시키는 물뿌리개를 사용해야 하는 횟수가 더 많아지므로 결론 2를 만족시킬 수 없다.

2만큼 성장시킬 수 있는 물뿌리개를 사용할 수 있는 횟수 >= 나무가 자라나는 데 걸리는 총 일수

 

!!!포인트!!!

2만큼 성장시키는 물뿌리개와 1만큼 성장시키는 물뿌리개가 사용되는 횟수는 같고, 물뿌리개 2를 이용해서 성장시킬 수 있는 나무는 쪼개서 물뿌리개 1도 사용 가능하기 때문에 2를 기준으로 생각하는 것이 중요!!! 2가 되면 1도 됨.

또, 전체 나무들의 높이를 더한 값이 3의 배수일 때(1+2) 3으로 나눈 몫이 주어진 나무들이 자라나는 데 걸리는 일수였다. 이 때, 2로 나눈 몫이 3으로 나눈 몫보다 커야하는 이유는 물뿌리개 2를 사용할 수 있는 횟수가 총 성장 일수보다 작다는 것은 1을 더 많이 사용해야 하는 것이라서 제시된 조건과 맞지 않기 때문이다.

 

 

 

내가 막혔던 부분

 

- 처음에 규칙성을 찾기가 어려워서 많이 헤맸다.

 

 

 

문제 풀이 방법

 

(1) 사과 나무의 개수 N과 N개 만큼의 사과나무 높이들을 입력받아 리스트에 저장하기

(2) 만약 사과나무들의 높이가 3의 배수라면 결론 2(위 문제 접근 방법 참고)를 판별하고 그렇지 않으면 불가능하다는 뜻이므로 "NO" 출력하기

(3) 3의 배수일 때는 리스트 h에 들어있는 사과나무들의 높이를 차례차례 2로 나눈 몫을 변수 cnt에 누적해서 더하기

(4) 2로 나눈 몫의 합이 사과나무들의 높이를 더한 값을 3으로 나눈 몫보다 크거나 같으면 조건 성립이므로 "YES" 출력하기

그렇지 않다면 "NO" 출력하기

 

 

 

소스코드

N = int(input())    # 사과나무의 개수

h = list(map(int, input().split())) # 나무의 높이

cnt = 0
if sum(h) % 3 == 0:
    for i in h:
        cnt += i // 2
    if cnt >= (sum(h) / 3):
        print("YES")
    else:
        print("NO")
else:
    print("NO")