글 읽기 - (pypy3) 시간을 더 줄일 수 있는 방법이 있는지 궁금합니다.

hcjy97 2년 전 0

sort는 처음에 trees를 입력받은 후 한 번만 하고

새로운 나무가 생성될 때 appendleft로 추가하여 오름차순을 유지했습니다.

아마 20, 39번째 줄에서 copy하는 게 문제인 것 같기는 한데 copy를 아예 하지 않고 문제를 풀 방법을 찾지 못했습니다.

spring함수에서 copy를 하지 않고

global에 있는 trees에서 직접 popleft()를 진행하는 방법도 사용해 봤는데

trees가 빈 배열인 상태로 fall 함수로 넘어가 에러가 나더군요..

copy를 사용하는 상태에서 시간을 더 줄일 수 있는 방법이 있을지 궁금합니다.

from collections import deque
import math

n, m, k = map(int, input().split())
land = [[5]*n for _ in range(n)]
a = [list(map(int, input().split())) for _ in range(n)]
trees = [list(map(int, input().split())) for _ in range(m)]

for i in range(len(trees)):
    trees[i] = [trees[i][0]-1, trees[i][1]-1, trees[i][2]]

def copy(q):
    newq = deque()
    for i in q:
        newq.append(i)
    return newq

def spring(trees):
    global land
    tq = copy(trees)
    death, alive = deque(), deque()
    for cx, cy, cz in tq:
        if land[cx][cy] < cz:
            death.append([cx, cy, cz])
        else:
            land[cx][cy] -= cz
            alive.append([cx, cy, cz+1])
    return death, alive

def summer(death):
    global land
    for cx, cy, cz in death:
        land[cx][cy] += math.trunc(cz / 2)


dxy = [(-1, -1), ( -1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
def fall(alive):
    global n, m, dxy
    tmp = copy(alive)
    for cx, cy, cz in tmp:
        if not cz % 5:
            for dx, dy in dxy:
                nx, ny = cx+dx, cy+dy
                if 0 > nx or 0 > ny or n <= nx or n <= ny:
                    continue
                alive.appendleft([nx, ny, 1])
    return alive

def winter():
    global n, land, a
    for x in range(n):
        for y in range(n):
            land[x][y] += a[x][y]

trees.sort(key=lambda x: (x[0], x[1], x[2]))
trees = deque(trees)
while k > 0:
    death, alive = spring(trees)
    summer(death)
    trees = fall(alive)
    winter()
    k -= 1
print(len(trees))

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

문제

문제

출처

ICPC

(pypy3) 시간을 더 줄일 수 있는 방법이 있는지 궁금합니다.

hcjy97 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말