Python으로 푸는 백준 16235. 나무 재테크

백준 16235. 나무 재테크

상도는 나무로 재테크를 하기 위해서 

묘목을 심어 영양분을 공급하고 5년마다 번식시킨다.

K년이 지난 후 땅에 살아있는 나무의 수가 얼마인지 계산하는 프로그램을 짜시오.

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

github에서 코드 보기

문제 조건

모든 땅에는 초기에 5만큼의 영양분이 공급되어 있다.

봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 

여름에는 봄에 영양분이 부족해서 먹지못한 나무가 죽어서 나이의 반만큼 (소수점은 버리고) 그 땅의 영양분이 된다.

가을에는 5살 터울로 나무가 인접한 칸 8개의 위치에 1살짜리 나무로 번식한다.

겨울에는 미리 입력받은 만큼 땅에 양분을 추가 공급해준다. (나무가 없는 땅에도 계속 공급해서 쌓아준다)

문제 해결하기 - 예제 7,8 오답

나무가 죽은 나무가 영양분이 되고, 새로운 나무를 번식하는 과정에서 나무를 추가하고 빼는게 잘 짜여져 있다면 문제는 땅에 있는 영양분의 수치다.

그 이전까지는 영양분의 수치가 미묘하게 달라도 나무에 영양분을 공급해줄 수 있을 만큼 영양분이 있었다면, 3년, 4년째부터는 죽는 나무가 생기기 때문에 영양분 계산을 잘 해주지 않으면 그 다음 해에는 예정에 없던 나무가 죽게 되버린다. 아래 이미지를 참고해서 매년 겨울까지 마치고 나서, 유지되어야 하는 영양분의 수치가 일치하는지 알아볼 수 있다.

문제 해결하기 - 시간 초과

리스트의 첫번째 요소를 pop(1)하고 있는가?

나무 나이 정보를 배열에 저장한 다음에 맨 처음 원소를 pop(1)하거나 오름차순으로 나무의 나이를 저장하고 싶어서 1살짜리 나무를 추가할때 맨 앞에 원소를 추가하고 있다면 당연히 시간 초과가 날 수 밖에 없다.  파이썬에서 첫번째 요소를 pop(1), insert() 할 경우에는 얼마만큼 시간 복잡도가 걸리는지 <Python 내장 함수의 시간 복잡도>에서 알 수 있다.

젤 어린 나무들 부터 영양분을 주기 위해서 정렬을 어떻게 하고 있는가?

나는 젤 어린 나무들부터 영양분을 주어야 하기 때문에 내림차순으로 나무의 나이 정보를 저장해뒀다. 즉, index가 0인 원소가 젤 나이가 많은 나무가 되고 맨 마지막 원소는 젤 나이가 어린 나무가 된다. 파이썬은 리스트에서 가장 마지막 원소를 pop() 하는 경우에는 시간 복잡도가 O(1)이다.

대신 영양분을 먹고 나이를 증가시켜야 하는 나무들을 위해 temp_trees를 만들어서 임시로 저장한 다음에 맨 마지막에 본래 배열에 extend() 한 후에 오름차순으로 정렬했다. 파이썬 내장 함수의 정렬 알고리즘은 O(n log n)이므로 효율이 나쁘지 않고, 봄,여름,가을, 겨울 다 거치면서 칸 별로 딱 한번 정렬을 하기 때문에 리스트의 첫번째 원소를 pop()하는 것보다는 훨씬 빠르게 코드가 돌아간다.

copy.deepcopy를 사용하고 있는가?

나는 나무가 번식하는 걸 코드로 짜기 위해서 기존 나무 정보가 담긴 dictionary를 deepcopy하여 사용하였다. deepcopy를 했던 이유는 너무 초기 코드라서 설명하기가 복잡하다. 여튼 이 문제에서는 deepcopy를 사용할 필요 없이 짤 수 있으며, 알고리즘이 정확하다면 deepcopy를 없애려는 노력만 하더라도 시간 초과는 피할 수 있을 거라고 생각한다.

문제 풀이

문제를 이해하고 코드를 짜는데는 큰 어려움이 없다. 하지만 시간 복잡도를 고려하지 않고 코드를 짰다면 시간 초과를 만나기 참 쉽다. 난 처음부터 고려하고 짠건데도 시간 초과가 났었다. (이런..)  나는 봄, 여름, 겨울을 한번에 처리해주었고, 번식을 해야만 하는 가을만 분리해서 반복문을 돌렸다. 영양분 수치와 관련 있는 계절을 모아서 한번에 처리한 것이다. 그리고 번식하거나 나무가 죽을때마다 미리미리 생존한 나무의 수를 계산해두었다. 

코드 리뷰

파이썬으로 통과한 사람이 2명 밖에 없고 그 중에서도 꽤 빠른 속도로 문제를 통과한 사람이 있었기에 끝까지 리팩토링을 진행해보았다. 이미 pypy를 통해서 알고리즘 자체가 틀리진 않았단 것을 검증해 놓고 있었기 때문에 리팩토링에 힘썼던 거기도 하다. (사실 같은 알고리즘이라도 파이썬이라서 시간 초과가 나는거라서 난 이 문제가 그닥 좋은 문제라고는 생각하진 않는다)

파이썬 코드

import sys
from collections import defaultdict
input = sys.stdin.readline
 
tree_count = 0
 
def solve(board, nutritions, tree_dict, k):
    """
    :param board : 밭
    :param nutritions: 겨울마다 주는 양분
    :param tree_dict: 위치별 나무들의 나이정보
    :param k: 년도
    :return: 남은 나무들의 수
    """
    global tree_count
    num = 0
    dr = [-1, -1, -1, 0, 0, 1, 1, 1]
    dc = [-1, 0, 1, -1, 1, -1, 0, 1]
 
    # k년이 흐를때까지
    while num < k:
 
        # 봄, 여름, 겨울을 한번에 처리해준다
        for i in range(n*n):
            r = i // n
            c = i % n
 
            nutrition = board[r][c]
            add_nutrition = 0
            trees = tree_dict[(r, c)]
 
            # 심어진 나무가 없으면 영양분만 공급한다
            if not trees:
                add_nutrition += nutritions[r][c]
                add_nutrition += nutrition
                board[r][c] = add_nutrition
                continue
 
            cnt = len(trees)
            temp_trees = []
            # 본 & 여름
            while 0 < cnt:
                tree = trees.pop()
                checked = nutrition - tree
                # 양분이 남아 있는지 여부 판단
                if 0 <= checked:
                    # 양분을 먹는다
                    nutrition -= tree
                    # 나이를 증가시키고, 임시 배열에 넣어준다
                    temp_trees.append(tree + 1)
                else:
                    # 유효하지 않으므로, 나무 죽이기
                    add_nutrition += (tree // 2)
                    tree_count -= 1
                cnt -= 1
            # 성장한 나무들을 기존 배열에 추가해준다
            trees.extend(temp_trees)
 
            if 1 < len(trees):
                trees.sort(reverse= True)
 
            # 겨울 (양분 추가)
            add_nutrition += nutritions[r][c]
            # 남은 양분이 있으면 추가
            add_nutrition += nutrition
            # 보드에 기록
            board[r][c] = add_nutrition
 
        # 가을
        for key, value in tree_dict.items():
            spread_tree_count = 0
            if len(value) == 0:
                continue
 
            for i in value:
                # 젤 큰 나무가 5보다도 작으면 패쓰
                if i < 5:
                    break
                if i % 5 == 0:
                    spread_tree_count += 1
 
            if spread_tree_count > 0:
                r, c = key
            for d in range(8):
                temp_r = r + dr[d]
                temp_c = c + dc[d]
                if 0 <= temp_r < n and 0 <= temp_c < n:
                    # 주변에 나무 번식
                    tree_count += spread_tree_count
                    tree_dict[(temp_r, temp_c)].extend([1]*spread_tree_count)
        # 해를 보낸다
        num += 1
    print(tree_count)
    return tree_count
 
if __name__ == "__main__":
    n, m, k = map(int, input().split())
    nutritions = []
    board = [[5]*n for _ in range(n)]
 
    for i in range(n):
        nutritions.append(list(map(int, input().split())))
 
    # 위치를 key로 하는 나무들의 정보를 배열에 저장한다.
    tree_dict = defaultdict(lambda :[])
    for t in range(m):
        r, c, old = map(int, input().strip().split())
        tree_dict[(r-1,c-1)].append(old)
        tree_count += 1
    solve(board, nutritions, tree_dict, k)
 

이미지로 보는 영양분 계산하기

#백준 16235. 나무 재테크 #백준 16235 파이썬  #백준 나무 재테크 python