나무 재테크 [16235] with 파이썬

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

16235번: 나무 재테크

 

n (땅 넓이)

m (나무개수)

k (종료 년)

n개 줄 -> A[r][c]

m개 줄 -> 나무 정보 (x,y 위치, z 나이)

 

봄 –  양분 -= 나이 / 나이 += 1 / 어린 나무 먼저 양분 흡수 (정렬)

 

여름 – 양분 += 죽은 나무 나이 // 2

 

가을 – 나이 % 5 == 0: -> 8방향에 나이 1 나무 추가 / 벗어나면 추가 X

 

겨울 – A[r][c] 만큼 양분 추가

 

K년 후 나무 개수 출력

------------------

 

# 시간 초과...

 

n,m,k = map(int, input().split())

# 땅 양분 상태
land = [[5]*n for _ in range(n)]

# 겨울에 추가되는 양분
a = [list(map(int, input().split())) for _ in range(n)]

# x,y : 위치 / z : 나이
trees = []
for i in range(m):
    trees.append(list(map(int, input().split())))
    trees[i][0] -= 1
    trees[i][1] -= 1

tree_cnt = [[0]*n for _ in range(n)]
for tree in trees:
    tree_cnt[tree[0]][tree[1]] += 1

dead_trees = [[0]*n for _ in range(n)]
dead_trees_idx = []

def spring():
    trees.sort()
    save_data = []
    for i in range(len(trees)):
        x = trees[i][0]
        y = trees[i][1]
        z = trees[i][2]

        if land[x][y] - z >= 0:
            land[x][y] -= z
            trees[i][2] += 1
        else:
            dead_trees[x][y] += (z // 2)
            dead_trees_idx.append((x,y))
            tree_cnt[x][y] -= 1
            save_data.append([x,y,z])
    for x,y,z in save_data:
        trees.remove([x,y,z])

def summer():
    if dead_trees_idx:
        for x, y in dead_trees_idx:
            land[x][y] += dead_trees[x][y]

def fall():
    dirs = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
    for x, y, z in trees:
        if z % 5 == 0:
            for dx, dy in dirs:
                nx = x + dx
                ny = y + dy

                if 0 <= nx < n and 0 <= ny < n:
                    tree_cnt[nx][ny] += 1
                    trees.append([nx,ny,1])

def winter():
    for i in range(n):
        for j in range(n):
            land[i][j] += a[i][j]

year = 0
while year != k:
    spring()
    summer()
    fall()
    winter()
    year += 1

total = 0
for i in range(n):
    total += sum(tree_cnt[i])
print(total)