글 읽기 - PyPy3에서는 통과되는데 Python3에서 시간 초과가 뜹니다.

martin0327 5년 전 0

어디서 속도를 높일 수 있을지 조언 부탁드립니다. 주석을 최대한 많이 달아뒀습니다.

#%% Input Reading for Submission

from collections import deque
 
N, M, K = map(int, input().split())

winter_nutr = []
for i in range(N):
    winter_nutr.append(list(map(int,input().split())))

nutr = [[5]*N for _ in range(N)]        

trees = {} # 나무 dict 생성

for i in range(N):
    for j in range(N):
        trees[(i,j)] = deque() #각 (i,j)에 deque 생성

for i in range(M):
    x,y,age = map(int,input().split())   # x,y인지 y,x인지 확인 필요
    trees[(x-1,y-1)].append(age)    # 초기 나무 저장
     
dead_trees = {} # 죽은 나무 dict 생성
 
for i in range(N):
    for j in range(N):
        dead_trees[(i,j)] = []   # 각 (i,j)에 죽은 나무 list 생성


#%%

def spring():
    for i in range(N):
        for j in range(N):
            tree_queue = trees[(i,j)]
            new_queue = deque()
            while tree_queue:
                tree = tree_queue.pop()  #오른쪽에 있을 수록 어린 나무
                if tree <= nutr[i][j]:  #양분이 충분
                    nutr[i][j] -= tree
                    new_queue.appendleft(tree+1) #나이가 많을 수록 왼쪽에 저장
                else: #양분이 불충분
                    dead_trees[(i,j)].append(tree//2)  #죽은 나무의 나이의 절반을 양분으로 저장
            trees[(i,j)] = new_queue     # deque 갱신

def summer():
    for i in range(N):
        for j in range(N):
            nutr[i][j] += sum(dead_trees[(i,j)])  #죽은 나무로 양분 보충
            dead_trees[(i,j)] = []                #죽은 나무 list 초기화
            
def autumn():
    all_dir = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] # 주위 8방향
    for i in range(N):
        for j in range(N):
            tree_list = list(trees[(i,j)]) #(i,j)에 있는 tree deque를 list로 변환
            for tree in tree_list:
                if tree % 5 == 0:  #5의 배수인지 확인
                    for di,dj in all_dir: # (i,j) 주위 8방향에 대해
                        if 0 <= i+di <= N-1 and 0 <= j+dj <= N-1:  #지도 바깥으로 안 나가는지 확인
                            trees[(i+di,j+dj)].append(1)           #나이가 1인 나무 저장

def winter():
    for i in range(N):
        for j in range(N):
            nutr[i][j] += winter_nutr[i][j]  # 양분 업데이트
        
def count_trees(): # 지도 전체의 나무 개수 확인
    count = 0
    for i in range(N):
        for j in range(N):
            count += len(trees[(i,j)]) 
    return count
#%%
def main():
    for _ in range(K): # 봄 여름 가을 겨울 K년 반복
        spring()
        summer()
        autumn()
        winter()
    print(count_trees())
#%%
if __name__ == "__main__":
    main()

jh05013 5년 전 0

파이썬이 극도로 느린 언어이기 때문에, 시간 내에 통과가 안 된다고 이상할 게 전혀 없습니다.

함수 호출이 느린 편이라서 그걸 제거해 주는 방법으로 속도를 향상시킬 순 있을 것 같습니다.

vega 5년 전 1

삼성 시험장도 pypy입니다!

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

문제

문제

출처

ICPC

PyPy3에서는 통과되는데 Python3에서 시간 초과가 뜹니다.

martin0327 5년 전 0

jh05013 5년 전 0

vega 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말