[백준 #16235] 나무 재테크

1. 문제 설명

2. 해설

코테 스터디 하면서 풀다가 시간초과나서 어디서 효율성이 안좋지? 고민을 오래 했고, 이제서야 풀었다... 배열 한개에 나무 정보를 담아서 처리하니 시간초과가 났고, 그래서 그냥 3차원 배열을 만들었다.

✨ 접근 방법

1. tree = [[[] for _ in range(N)]for _ in range(N)] 라는 나무 정보를 입력받을 3차원 배열을 선언하고, tree[x-1][y-1]에 나무 정보를 append하면 된다.

2. 나이가 어린 나무부터 양분을 먹으므로, 정렬을 해준 뒤에 봄 로직을 처리한다. (2중 for문 활용)

3. 여름에는 봄에 죽은 나무의 나이를 2로 나눈 값이 땅에 양분으로 추가된다.

4. 가을에는 나이가 5의 배수인 나무 주변 8칸에 나무가 번식한다.

5. 겨울에는 S2D2 로봇이 돌아다니면서 땅에 입력받은 만큼의 양분을 추가한다.

6. 위의 사이클을 K번 반복한다.

자 이제 위의 로직을 코드로 구현해보자.

3. 코드

from sys import stdin, exit
input = stdin.readline


def spring_and_summer():
    # 봄에는 나무가 자기 나이만큼 양분을 먹고 1살 자람
    for x in range(N):
        for y in range(N):
            if tree[x][y]:
                tree[x][y].sort()  # 나이가 어린 나무부터 양분 섭취

                dead, alive = 0, []
                for t in tree[x][y]:
                    # 양분을 섭취할 수 없다면 그 나무는 즉시 죽고, 여름에 나무의 나이 // 2만큼의 양분을 땅에 추가
                    if t > land[x][y]:
                        dead += t // 2
                    else:  # 살아남은 나무는 따로 배열에 추가하고, 로직 처리함
                        land[x][y] -= t
                        t += 1
                        alive.append(t)

                # 여름 - 봄에 죽은 나무의 나이 // 2만큼 양분 추가,
                land[x][y] += dead
                tree[x][y] = alive


# 가을에는 나이가 5의 배수인 나무 주변 8칸에 나무 번식
def fall():
    dx = [1, 0, -1, 0, 1, -1, -1, 1]
    dy = [0, 1, 0, -1, 1, 1, -1, -1]

    for x in range(N):
        for y in range(N):
            if tree[x][y]:
                for t in tree[x][y]:
                    if t % 5 == 0:
                        for d in range(8):
                            ax = x + dx[d]
                            ay = y + dy[d]
                            if 0 <= ax < N and 0 <= ay < N:
                                tree[ax][ay].append(1)


# 겨울에는 S2D2 로봇이 돌아다니며 땅에 양분 추가
def winter():
    for x in range(N):
        for y in range(N):
            land[x][y] += felt[x][y]


N, M, K = map(int, input().split())
land = [[5] * N for _ in range(N)]
felt = [list(map(int, input().split())) for _ in range(N)]
tree = [[[] for _ in range(N)] for _ in range(N)]

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


for _ in range(K):
    spring_and_summer()
    if not tree:  # 봄에 나무가 모두 죽었을 경우
        print(0)
        exit()
    fall()
    winter()

res = 0
for i in range(N):
    for j in range(N):
        res += len(tree[i][j])

print(res)