파이썬으로 풀어보는 백준 16235번: 나무 재테크 (삼성 A형 기출 문제)

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

16235번: 나무 재테크

 

내 풀이:

def go():
    die = []
    for t in tree:
        z = t[0]
        y = t[1]
        x = t[2]
 
        if arr[y][x] - z >= 0:
            arr[y][x] -= z
            t[0] += 1
        else:
            die.append(t)
 
    for di in die:
        tree.remove(di)
        z = di[0]
        y = di[1]
        x = di[2]
        arr[y][x] += (z//2)
 
    new = []
    for t in tree:
        z = t[0]
        if z % 5 == 0:
            y = t[1]
            x = t[2]
 
            for dir in range(8):
                ny = y + dy[dir]
                nx = x + dx[dir]
 
                if 0 <= ny <= N-1 and 0 <= nx <= N-1:
                    new.append([1, ny, nx])
 
    for a in new:
        tree.insert(0, a)
 
    for i in range(N):
        for j in range(N):
            arr[i][j] += feed[i][j]
 
 
N, M, K = map(int,input().split())
feed = [list(map(int,input().split())) for _ in range(N)]
arr = [[5] * N for _ in range(N)]
tree = []
 
dy = [1, 1, 1, 0, 0, -1, -1, -1]
dx = [-1, 0, 1, -1, 1, -1, 0, 1]
 
for _ in range(M):
    x, y, z = map(int,input().split())
    tree.append([z, y-1, x-1])
tree.sort()
 
for year in range(K):
    go()
 
print(len(tree))

PyPy3, 시간 초과

봄, 여름, 가을, 겨울 각각의 조건을 하나의 사이클로 코드를 구현하였다. 주의해야할 점은 나무가 죽자마자 양분을 추가해주면 문제 조건에 맞지 않다는 점이다. 때문에 나무가 죽었을 때 죽은 나무를 따로 저장해서 처리하여야 하는 것이 시간 초과에 가장 큰 원인이 된다고 생각한다.

 

 

def go():
    global tree
    die = []
    birth = []
    for t in tree:
        z = t[0]
        y = t[1]
        x = t[2]
 
        if arr[y][x] - z >= 0:
            arr[y][x] -= z
            t[0] += 1
            if t[0] % 5 == 0:
                birth.append(t)
        else:
            die.append(t)
 
    for di in die:
        tree.remove(di)
        z = di[0]
        y = di[1]
        x = di[2]
        arr[y][x] += (z//2)
 
    for t in birth:
        y = t[1]
        x = t[2]
 
        for dir in range(8):
            ny = y + dy[dir]
            nx = x + dx[dir]
 
            if 0 <= ny <= N-1 and 0 <= nx <= N-1:
                tree.insert(0, [1, ny, nx])
 
    for i in range(N):
        for j in range(N):
            arr[i][j] += feed[i][j]
 
 
N, M, K = map(int,input().split())
feed = [list(map(int,input().split())) for _ in range(N)]
arr = [[5] * N for _ in range(N)]
tree = []
 
dy = [1, 1, 1, 0, 0, -1, -1, -1]
dx = [-1, 0, 1, -1, 1, -1, 0, 1]
 
for _ in range(M):
    x, y, z = map(int,input().split())
    tree.append([z, y-1, x-1])
tree.sort()
 
for year in range(K):
    go()
 
print(len(tree))

PyPy3, 시간 초과

먼저 봄에 나무의 위치와 나이를 확인할 때 가을에 새로 태어날 나무를 미리 저장해두었다가 가을이 되면 다시 전체를 탐색할 필요없이 바로 추가해주는 방식으로 시간을 절약하였다.