[BOJ/백준] 16235 나무 재테크

from collections import deque
import sys
input = sys.stdin.readline
 
N,M,K = map(int,input().split())
 
 
AppendList = [list(map(int,input().split())) for _ in range(N)]
tree_info = [[[] for _ in range(N)] for _ in range(N)]
result = 0
forest = [[5]*N for _ in range(N)]
 
for _ in range(M):
    X,Y,age = map(int,input().split())
    tree_info[X-1][Y-1].append(age)
    result += 1
 
dx = [-1,-1,-1,0,0,1,1,1]
dy = [-1,0,1,-1,1,-1,0,1]
for year in range(K):
 
    for x in range(N):
        for y in range(N):
            if len(tree_info[x][y])>0:
                temp = []
                summer_forest = 0
                cnt = 0
                limited = len(tree_info[x][y])
                while cnt < limited:
                    age = tree_info[x][y].pop()
 
                    if forest[x][y] >= age:
                        forest[x][y] -= age
                        temp.append(age+1)
                    else:
                        summer_forest += (age//2)
                        result -= 1
                    cnt += 1
                temp.sort(reverse=True)
                tree_info[x][y].extend(temp)
                forest[x][y] += summer_forest
            forest[x][y] += AppendList[x][y]
    for x in range(N):
        for y in range(N):
            spread_cnt = 0
            if tree_info[x][y]:
                for val in tree_info[x][y]:
                    if val%5 == 0:
                        spread_cnt += 1
 
            if spread_cnt:
                for i in range(8):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<N and 0<=ny<N:
                        result += spread_cnt
                        tree_info[nx][ny].extend([1]*spread_cnt)
print(result)

 구현을 하는 문제인데, 문제에 주어진 조건대로 면 된다. 문제는 시간초과의 벽이 너무 컸다. 시간초과가 나지 않도록 최대한 문제에 주어진 조건을 한번에 구현할수 있도록 하는게 중요했다.

 

import sys
input = sys.stdin.readline
N,M,K  = map(int,input().split())
store = [list(map(int,input().split())) for _ in range(N)]
tree_info = [[{} for _ in range(N)] for _ in range(N)]
forest = [[5]*N for _ in range(N)]
 
tree_cnt = 0
for _ in range(M):
    x,y,age = map(int,input().split())
    tree_info[x-1][y-1][age] = 1
    tree_cnt += 1
 
dx = [-1,-1,-1,0,0,1,1,1]
dy = [-1,0,1,-1,1,-1,0,1]
 
for _ in range(K):
    for x in range(N):
        for y in range(N):
            if tree_info[x][y]:
                summer_forest = 0
                new_dict = {}
 
                for age in sorted(tree_info[x][y].keys()):
                    if forest[x][y] >= age * tree_info[x][y][age]:
                        forest[x][y] -= age * tree_info[x][y][age]
                        new_dict[age+1] = tree_info[x][y][age]
                    else:
                        if forest[x][y] // age:
                            new_dict[age+1] = forest[x][y]//age
                            forest[x][y] -=  age*new_dict[age+1]
                            if tree_info[x][y][age] - new_dict[age+1]:
                                summer_forest += (age//2) * (tree_info[x][y][age] - new_dict[age+1])
                                tree_cnt -= (tree_info[x][y][age] - new_dict[age+1])
                        else:
                            summer_forest += (age//2)*tree_info[x][y][age]
                            tree_cnt -= tree_info[x][y][age]
                tree_info[x][y] = new_dict
                forest[x][y] += summer_forest
            forest[x][y] += store[x][y]
    for x in range(N):
        for y in range(N):
            spread_cnt = 0
            for age in tree_info[x][y]:
                if not age%5:
                    spread_cnt += tree_info[x][y][age]
            if spread_cnt:
                for i in range(8):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx <N and 0<=ny<N:
                        if tree_info[nx][ny].get(1):
                            tree_info[nx][ny][1] += spread_cnt
                        else:
                            tree_info[nx][ny][1] = spread_cnt
                        tree_cnt += spread_cnt
print(tree_cnt)