16235_나무제테크

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

16235번: 나무 재테크

 

 

 

알고리즘보다는 문제를 얼마나 꼼꼼히 읽고 그대로 구현할 수 있냐 문제였다.

 

되게 어이없는부분에서 막혔었다...

 

나무가 양분을 먹지 못하는 경우 전체 나무양분의 절반을 가져간다고 생각했는데, 각 개별 나무의 나이의 절반을 양분을 흙에 되돌려 놓기 때문에 한번에 더하면 안된다. 예를들어

 

[3,3] 와같은 나무 두그루가 죽어야한다고 생각하면 한번에 처리하면

 

6 // 2 => 3의 양분이 흙으로 되돌아가야할것 같지만 실제로는 각 나무의 절반이므로

 

1 + 1 => 2의 양분이 흙으로 되돌아가야한다.

 

 

 

처음에는 heap이나 que를 쓸까 하다가 어차피 새로운 나무들을 뒤에 추가만 하면 될 것 같아 리스트로 풀었다.

import sys
input = sys.stdin.readline


n,m,k = map(int,input().split())
A = [ list(map(int,input().split())) for _ in range(n)]
trees = [ [ [] for _ in range(n)] for _ in range(n)]
ground = [ [5] * (n) for _ in range(n)]

for _ in range(m):
    x,y,z = map(int,input().split())
    trees[x-1][y-1].append(z)

dx = [-1,-1,-1,0,0,1,1,1]
dy = [-1,0,1,-1,1,-1,0,1]



for _ in range(k):
#봄,여름
    for i in range(n):
        for j in range(n):
            energy = 0
            for q in range(len(trees[i][j])):
                if trees[i][j][q] > ground[i][j]:
                    # energy = sum(trees[i][j][q:])
                    for die in trees[i][j][q:]:
                        energy += die//2
                    trees[i][j] = trees[i][j][:q]
                    break
                ground[i][j] -= trees[i][j][q]
                trees[i][j][q] += 1
            ground[i][j] += energy


    #가을
    for i in range(n):
        for j in range(n):
            for q in range(len(trees[i][j])):
                if trees[i][j][q]%5 ==0:
                    for d in range(8):
                        ni,nj = i +dx[d],j+dy[d]
                        if 0<=ni<n and 0<=nj<n:
                            trees[ni][nj].insert(0,1)
            ground[i][j] += A[i][j]
    #겨울




    # cnt = 0
    # print(f'============={_+1}년=============')
    # for i in trees:
    #     print(i)
    # print('--------------------------')
    # for i in ground:
    #     print(i)
    # for i in trees:
    #     for j in i:
    #         cnt += len(j)
    # print('cnt : ', cnt)

cnt = 0
for i in trees:
    for j in i:
        cnt += len(j)

print(cnt)