Intuition

시뮬레이션 유형이므로 하라는대로 했을 때 시간이 초과할지 먼저 체크했습니다. 시간복잡도가 아슬아슬해 보이긴 해도 초과할 것으로 보여지진 않았으므로 하라는대로 차근차근 구현했습니다.

Algorithm

1. 매년 봄, 여름, 가을, 겨울이 반복된다.
2. 봄에는 3차원으로 관리하는 각 격자상의 나무들을 오름차순 정렬한 뒤, 나이만큼 영양소를 차감해주고 살아있는 나무 리스트에 추가한다. 만약 영양소가 부족한 나무는 죽은 나무 큐에 담아둔다. 선별이 완료되면 해당 격자에 살아있는 나무 리스트를 복사하고 다음 격자로 넘어감을 반복한다.
3. 여름에는 봄에 죽은 나무 큐를 순회하며 영양소 격자에 반영한다.
4. 가을에는 전체 격자에 대하여 나무의 나이가 5의 배수인 격자의 8방으로 나이가 1인 나무를 3차원 격자 리스트에 추가해준다.
5. 겨울에는 사전에 받아둔 배열을 이용하여 영양소 격자에 추가해준다.

from collections import deque
import sys
input = sys.stdin.readline

N, M, K = map(int, input().split()) # N 땅 크기, M 나무 개수, k 년 수
grid = [[5 for _ in range(N)] for _ in range(N)] # 기본 영양분 맵
bonus = [[] for _ in range(N)] # 추가 영양분 맵
tree = [[[] for _ in range(N)] for _ in range(N)] # 나무 정보 - 3차원 리스트
dead = deque()
dy = [-1, -1, -1, 0, 0, 1, 1, 1]
dx = [-1, 0, 1, -1, 1, -1, 0, 1]

for i in range(N):
    bonus[i] = list(map(int, input().split()))
for i in range(M):
    y, x, z = map(int, input().split())
    tree[y-1][x-1].append(z)

def in_range(y, x):
    return 0 <= y < N and 0 <= x < N

def spring():
    for y in range(N):
        for x in range(N):
            alive = []
            now_tree = sorted(tree[y][x])
            for z in now_tree:
                if grid[y][x] >= z:
                    alive.append(z+1)
                    grid[y][x] -= z
                else:
                    dead.append([y, x, z])
            tree[y][x] = alive.copy()

def summer():
    while dead:
        y, x, z = dead.pop()
        grid[y][x] += z // 2
def fall():
    for y in range(N):
        for x in range(N):
            for z in tree[y][x]:
                if z % 5 == 0:
                    for i in range(8):
                        if in_range(y + dy[i], x+dx[i]):
                            tree[y+dy[i]][x+dx[i]].append(1)
def winter():
    for y in range(N):
        for x in range(N):
            grid[y][x] += bonus[y][x]
    return

def simulation():
    spring()
    summer()
    fall()
    winter()

def get_answer():
    ans = 0
    for y in range(N):
        for x in range(N):
            ans += len(tree[y][x])
    return ans

for _ in range(K):
    simulation()
print(get_answer())

Complexity Analysis

• 시간복잡도 : O(N^2 M K)
• 공간복잡도 : O(N^3)