문제 링크

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

문제 설명

• 몇 년 키울지, 초기에 심을 나무 정보, 매년 추가될 양분 정보가 주어짐
• 봄에는 나이 순으로 양분을 먹고 나이를 먹음
• 여름에는 양분을 먹지 못한 나무가 죽음
• 가을에는 나무들이 번식해 1살 나무가 추가됨
• 겨울에는 양분을 추가해줌

풀이

• 그대로 구현하면 되지만 좌표별 나무의 나이순 정렬을 유지하는 것이 중요하다
• 추가될 나무가 1살이라 항상 최솟값이기 때문에 deque를 사용해 appendleft 해준다
• 이렇게 하면 특정 좌표의 나무를 탐색하고 정렬을 유지하는데 O(N)으로 가능하다
  • N : 특정 좌표의 나무 개수

후기

• 처음에 heapq로 정렬을 유지했는데 시간초과 났다
• deque에서 양분에 부족할 때 죽는 나무를 바로 양분에 더해줘서 헤맸다
• 양분 값이 달라져서 이후에 죽는 나무가 달라진다

코드

def spring_summer():
    for i in range(n):
        for j in range(n):
            new_tree = deque()
            while tree[i][j]:
                curr = tree[i][j].popleft()
                if food[i][j] >= curr:
                    food[i][j] -= curr
                    new_tree.append(curr + 1)
                else:
                    tree[i][j].appendleft(curr)
                    break
            while tree[i][j]:
                curr = tree[i][j].popleft()
                food[i][j] += curr // 2
            tree[i][j] = new_tree


def fall():
    for i in range(n):
        for j in range(n):
            for y in tree[i][j]:
                if y % 5 == 0:
                    append_tree(i, j)


def append_tree(cy, cx):
    dy = [0,0,-1,1,-1,1,-1,1]
    dx = [1,-1,0,0,-1,1,1,-1]
    for d in range(8):
        ny, nx = cy + dy[d], cx + dx[d]
        if 0 <= ny < n and 0 <= nx < n:
            tree[ny][nx].appendleft(1)


def winter():
    for i in range(n):
        for j in range(n):
            food[i][j] += added_food[i][j]
            

def get_answer():
    answer = 0
    for i in range(n):
        for j in range(n):
            answer += len(tree[i][j])
    return answer


# init
from collections import deque
import sys, heapq
read = sys.stdin.readline
n, m, k = map(int, read().split())
added_food = [list(map(int, read().split())) for _ in range(n)]
food = [[5]*n for _ in range(n)]
tree = [[deque() for _ in range(n)] for _ in range(n)]
inputs = [list(map(int, read().split())) for _ in range(m)]
for y, x, year in inputs:
    tree[y-1][x-1].append(year)

# start
for y in range(k):
    spring_summer()
    fall()
    winter()
print(get_answer())