[Python/파이썬] - 백준(BOJ) 16235번 : 나무 재테크

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

16235번: 나무 재테크

 

 

골드4 주제에 시간초과 최적화 때문에 매우 매우 골치아팠던 문제.

Pypy3으로 컴파일 해야한다.

 

우선 오답 풀이로는 봄을 처리할 때 tree를 3중배열 처리 하지 않고 tree[index]에 age, y, x를 저장하여

모든 tree 탐색을 하며 원소를 pop하고 잠시 temp 배열에 저장한 후 봄 처리가 끝나면 다시 tree에 저장했다.

이렇게 하면 pop과 append를 원소 개수마다 한번씩 사용하였던 것이 문제였던 것 같다.

 

정답 풀이로는 tree를 3중배열 처리하여 tree[y][x].append(age)로 원소를 추가해야 한다. 

그리고 봄 처리할 때 만약 영양분보다 tree[y][x][k]의 age가 크면 인덱스 k부터 뒤의 모든 나무를 pop하면 된다.

왜냐하면 처음 나무 정보를 받을 때 같은 위치의 나무는 주어지지 않으므로 가을 처리할 때

새로운 원소를 appendleft를 사용해서 넣는다면 무조건 어린 나무가 앞에 있도록 sort되기 때문이다.

 

진작 고집을 버리고 Java로 풀었다면 더 빨리 풀었을까 싶기도 했다.

이 코드를 짜고 임의로 테스트케이스를 돌렸을 때 속도가 더 느리게 나와서 제출하지 않다가 혹시나 해서 제출했더니 맞았다.

앞으로는 임의 테스트케이스 처리 속도가 더 느리다고 제출하지 않는 멍청한 짓은 하지 말아야겠다.

 

 

import sys
from collections import deque
input = sys.stdin.readline

def year():
    for i in range(n):
        for j in range(n):
            for k in range(len(tree[i][j])):
                # spring
                if land[i][j] >= tree[i][j][k]:
                    land[i][j] -= tree[i][j][k]
                    tree[i][j][k] += 1
                    if tree[i][j][k]%5 == 0:
                        prod.append([i, j])
                # summer
                else:
                    for x in range(len(tree[i][j])-1, k-1, -1):
                        land[i][j] += tree[i][j][x] // 2
                        tree[i][j].pop()
                    break
    # fall
    dy = [-1, -1, -1, 0, 0, 1, 1, 1]
    dx = [-1, 0, 1, -1, 1, -1, 0, 1]
    while prod:
        y, x = prod.pop()
        for i in range(8):
            yy = y + dy[i]
            xx = x + dx[i]
            if 0 <= yy < n and 0 <= xx < n:
                tree[yy][xx].appendleft(1)
    # winter
    for i in range(n):
        for j in range(n):
            land[i][j] += arr[i][j]

n, m, k = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
land = [[5 for _ in range(n)] for _ in range(n)]
tree = [[deque([]) for _ in range(n)] for _ in range(n)]
prod = []
answer = 0

for i in range(m):
    x, y, z = map(int,input().split())
    tree[x-1][y-1].append(z)
for i in range(k):
    year()
for i in range(n):
    for j in range(n):
        answer += len(tree[i][j])
print(answer)