[BOJ] 19539: 사과나무 (Python

문제 링크

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

풀이 전략

Math

⏰ 49분 ⏰

규칙성을 찾기가 힘들어서 많이 해맸습니다.
문제를 해결한 후 검색을 해 보니, 따로 공식을 구해 푸신 분들이 많았습니다. 다른 공식을 이용한 풀이법은 마지막 부분에 첨부했습니다.

일단, 모든 사과나무의 높이는 3의 배수여야 합니다.
하지만 여기서 한 가지 고려할 사항이 있는데요, 모든 사과나무의 높이의 합이 3의 배수라고 하더라도 각 사과나무에 할당되는 +2짜리 물뿌리개로 물을 뿌리는 횟수의 합이 모든 사과나무를 3으로 나눈 몫/2보다 작다면, 주어진 입력대로 배치할 수 없습니다.
모든 경우에서 +1짜리 물뿌리개와 +2짜리 물뿌리개는 동일한 횟수여야 하기 때문이죠.

즉, 주어진 입력이 가능하려면

1. 모든 입력값의 합이 3의 배수여야 하고

2. 각각의 입력값을 2로 나눈 몫이 모든 입력값의 합을 3으로 나눈 몫의 절반보다 같거나 커야 합니다.

이 로직을 코드로 구현했습니다.

구현

if __name__ == "__main__":
    n = int(input())
    trees = list(map(int, input().split()))
    tree_sum = sum(trees)
    
    # 모든 사과나무를 3으로 나눈 몫
    cnt = tree_sum // 3
    
    if tree_sum % 3 != 0:
        print('NO')

    else:
    	# 2짜리 물뿌리개로 물을 뿌리는 횟수 계산
        for tree in trees:
            cnt -= tree//2

        if cnt>0:
            print('NO')
        else:
            print('YES')

삽질

모든 사과나무의 높이는 3의 배수여야 한다는 것은 파악해서,
나무의 길이를 전부 더해 3으로 나눈 나머지를 less라는 배열에 저장했습니다.
여기서 일차적으로 가능 여부를 판단했습니다.

다음으로 less배열이 같은 수의 1과 2로 이루어져있다면 가능한 것으로 판단했습니다.

하지만, 오류 검증을 통해 반례가 많은 잘못된 방법이라는 것을 깨달았습니다.

if __name__ == "__main__":
    n = int(input())
    trees = list(map(int, input().split()))
    less = [0]*(n+1)

    if n == 1:
        if trees[0]%3 == 0:
            print('YES')
        else:
            print('NO')
    else:
        for i in range(n):
            less[i] = trees[i]%3
        if less.count(1) == less.count(2):
            print('YES')
        else:
            print('NO')

참고 풀이법

Library of Koreandria님의 블로그