Baekjoon_16235_나무재테크

16235번: 나무 재테크

 

 

시간초과 코드

from collections import deque

def grow(year, tree):

    if year == K:
        cnt = 0
        for x, y, old in tree:
            if old > 0:
                cnt += 1
        print(cnt)
        return

    else:
        tree.sort(key=lambda x : x[2])
        dead = []
        # 봄
        for idx in range(len(tree)):
            x, y, old = tree[idx]
            # 나무가 살아있는지 확인
            if old <= 0:
                continue
            # 양분을 먹을 수 있는 조건이라면
            if nutri[x][y] >= old:
                # 양분 먹기
                nutri[x][y] -= old
                # 나이도 먹기
                tree[idx][2] += 1
            else:
                # 죽은 나무에 추가하기
                dead.append([x, y, old])
                # 나이를 0으로 변경 (죽음)
                tree[idx][2] = 0

        # 여름
        for idx in range(len(dead)):
            x, y, old = dead[idx]
            # 양분으로 변하기
            nutri[x][y] += old//2

        # 가을
        dq = deque(tree)

        while dq:
            x, y, old = dq.popleft()

            if old != 0 and old % 5 == 0:
                for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]:
                    nx, ny = x + dx, y + dy
                    # 상도의 땅을 벗어나지 않는 경우에
                    if 0 <= nx < N and 0 <= ny < N:
                        # 나이가 1인 나무가 생김
                        tree.append([nx, ny, 1])

        # 겨울
        for i in range(N):
            for j in range(N):
                nutri[i][j] += arr[i][j]

        grow(year+1, tree)


N, M, K = map(int, input().split())

arr = [list(map(int, input().split())) for _ in range(N)]

tree = []
for _ in range(M):
    # 나무의 위치 (x, y)와 나이 z
    x, y, z = map(int, input().split())

    tree.append([x-1, y-1, z])

# 양분이 담긴 배열
nutri = [[5] * N for _ in range(N)]

grow(0, tree)

세상 시간초과 나는 코드,,,ㅎ 집가서 다시 풀깅

 

 

해결방법

- 봄이 다 지나고 나서 양분으로 추가해 주어야한다. 죽은 나무의 양분을 dead 변수에 모아 두었다가 for문이 끝나면 양분에 추가해주기

- 살아있는 나무들을 리스트에 넣어두었다가 여름이 지나면 갱신해주기

N, M, K = map(int, input().split())

# 겨울에 줄 양분 배열
arr = [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
    x, y, z = map(int, input().split())
    TREE[x-1][y-1].append(z)

# 양분이 담긴 배열
nutri = [[5] * N for _ in range(N)]


for _ in range(K):
    for i in range(N):
        for j in range(N):
            if TREE[i][j]:
                # 나이가 어린 나무 부터 양분을 먹자
                TREE[i][j].sort()

                # 봄
                live, dead = [], 0
                for old in TREE[i][j]:
                    # 양분을 먹을 수 있는 조건이라면
                    if nutri[i][j] >= old:
                        # 양분 먹기
                        nutri[i][j] -= old
                        # 나이도 먹기
                        old += 1
                        live.append(old)
                    else:
                        # 여름
                        # 죽은 나무는 양분이된다
                        dead += old//2
                # 양분을 다 먹고 죽은 나무가 여름에 양분이 된다. for문 이후에 양분으로 추가해주기
                nutri[i][j] += dead

                TREE[i][j].clear()
                TREE[i][j].extend(live)

    # 가을
    for i in range(N):
        for j in range(N):
            for t in TREE[i][j]:
                if t % 5 == 0:
                    for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]:
                        ni, nj = i + di, j + dj
                        # 상도의 땅을 벗어나지 않는 경우에
                        if 0 <= ni < N and 0 <= nj < N:
                            # 나이가 1인 나무가 생김
                            TREE[ni][nj].append(1)
            # 겨울
            nutri[i][j] += arr[i][j]

cnt = 0
for i in range(N):
    for j in range(N):
        cnt += len(TREE[i][j])

print(cnt)