[백준] 16235.나무 재태크

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

문제 풀이

일단 계절 별 구현
3차원 tensor 이용해서 풀이
각 나무의 나이를 리스트에 저장해서 햇수를 반복하며 실행
1. 오답입니다 -> 5의 배수가 아닌 5 이상으로 알고 구현, 봄&여름에서 list에서 새로운 list를 이용했는데, remove를 여전히 사용하고 있어서 값의 변동이 있었다.
2. 시간초과 -> 반복문 내에서 동시에 처리할 수 있는 것들은 동시에 처리 ex)봄과 여름, 가을과 겨울은 한 번에 처리할 수 있으므로 한 번의 for문에서 처리, list대신 deque를 사용해서 appendleft()이용 - sort를 매번 해주지 않아도 됨, pypy3로 제출하기..ㅎ

정답 코드

"""
https://www.acmicpc.net/problem/16235
"""
# (r,x)는 graph의 좌표를 직접적으로 의미
# 양분은 모든 칸에 5씩
# 봄 : 어린 나무부터 해당 칸의 양분 먹기, 나이만큼 못 먹으면 죽음, 그 후에 나이 +1
# 여름 : 죽은 나무 -> 양분, 나이//2만큼 추가
# 가을 : 나이 5이상 나무 번식, 주변 칸에 나무 추가, 벗어나면 X
# 겨울 : 양분 추가 
# K년이 지난 후 살아있는 나무 개수
# 각 칸에 대해 존재하는 나무의 나이를 list에 추가
# 5이상이 아닌 5의 배수에서 번식
# 천년테케 통과 못함.. -> 통과
# 시간초과 해결 
# ->1. 반복문 중복 최대한 감소, 2. deque()사용,
# 3.input = sys.stdin.readline사용, 4. pypy3로 제출
import sys
from collections import deque
input = sys.stdin.readline
N,M,K = map(int,input().split())
nutr = [[5]*N for _ in range(N)]
add_nutr = [list(map(int,input().rstrip().split())) for _ in range(N)]
graph = [[deque() for _ in range(N)] for _ in range(N)] 
# 그냥 한 행에 대해서 곱해주면 모든 행이 같아지므로
# for문을 이용해서 독립적으로 생성해줘야함
for _ in range(M):
    x,y,age = map(int,input().rstrip().split())
    graph[x-1][y-1].append(age)
def year(graph,nutr):
    dx = [0,0,1,1,1,-1,-1,-1]
    dy = [1,-1,0,1,-1,0,1,-1]
    # spring, summer
    for i in range(N):
        for j in range(N):
            be_nutr = 0
            alive = deque()
            for age in graph[i][j]: # 양분 먹기
                if nutr[i][j]>=age:
                    nutr[i][j] = nutr[i][j] - age
                    alive.append(age+1) # 양분 먹은 나무는 나이+1
                else: # 양분 없어서 죽음
                    be_nutr += age//2
            nutr[i][j] += be_nutr # 죽은 나무 양분화
            graph[i][j] = alive # 나이 먹음
    # fall
    for i in range(N):
        for j in range(N):
            if graph[i][j]:
                for tree in graph[i][j]:
                    if tree%5==0: 
                    # 5이상이 아니라 5의 배수...;;
                        for k in range(8):
                            nx = i+dx[k]
                            ny = j+dy[k]
                            if 0<=nx<N and 0<=ny<N:
                                graph[nx][ny].appendleft(1)
            # winter
            nutr[i][j] += add_nutr[i][j]
    return graph, nutr
for _ in range(K):
    graph,nutr = year(graph,nutr)
answer = 0
for i in range(N):
    for j in range(N):
        answer += len(graph[i][j])
print(answer)

추가적인 개념 (optional)

시간 단축할 때는 무조건 시간 복잡도 함수를 낮추는 것이 중요하다. 그러나 레벨이 높아질 수록 사소한 차이로 시간초과가 날 수 있다.
실버 때는 시간 복잡도 함수가 달라지면 시간초과여부가 갈렸는데 이 문제는 3n^2, 2n^2에 따라 그 여부가 갈렸다.

😭