글 읽기 - pyhton3 시간 초과 질문드립니다

canoneod 2년 전 0

오버헤드라고 생각되는 부분들을 제거하고 sort도 사용하지 않았는데 자꾸 시간초과가 뜹니다.... 어디서 조언 주시면 감사히 받겠습니다.

from collections import deque

N, M, K = map(int, input().split()) # N: 크기, M : 초기 나무, K: 년 수
nutrients = [list(map(int, input().split())) for _ in range(N)]
board = [[5 for _ in range(N)] for _ in range(N)]
trees = {}

ans = 0 # 정답
for _ in range(M):
    y, x, age = map(int, input().split())
    y -= 1
    x -= 1
    trees[(y, x)] = deque([age])
    ans += 1

dir = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]


for year in range(K):
    newCoord = []
    # spring, summer
    for y, x in trees:
        nums = len(trees[(y,x)]) # current tree count
        idx = -1
        for i in range(nums): # age 순서대로 양분 흡수
            if trees[(y,x)][i] <= board[y][x]:
                idx = i
                board[y][x] -= trees[(y,x)][i] 
                trees[(y,x)][i] += 1
                if trees[(y,x)][i] % 5 == 0:
                    for dy, dx in dir:
                        if 0 <= y + dy < N and 0 <= x + dx < N:
                            ans += 1 # 새로 추가됨
                            newCoord.append((y+dy, x+dx))
            else:
                break     
        if idx == -1: # 나무가 다 죽는 경우
            for _ in range(nums):
                val = trees[(y,x)].pop()
                board[y][x] += val // 2 # 양분
            ans -= nums
        else:
            for _ in range(nums-idx-1):
                val = trees[(y,x)].pop()
                board[y][x] += val // 2 # 양분    
            ans -= (nums-idx-1) # 죽는 나무 수

    # autumn
    for y,x in newCoord:
        if (y,x) in trees:
            trees[(y,x)].appendleft(1)
        else:
            trees[(y,x)] = deque([1])
 
    # winter
    for i in range(N):
        for j in range(N):
            board[i][j] += nutrients[i][j]

print(ans)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

pyhton3 시간 초과 질문드립니다

canoneod 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말