글 읽기 - 코드50줄) 파이썬 시간초과..어디서 나는걸까요?

dlgydms96 3년 전 0

풀이방법은

1. 나무의 (x,y,나이)저장된 1차원 리스트 내림차순 정렬

2. 뒤의 원소부터 순회하며 양분을 먹을 수 있는지 체크

참이면, 나이+1, 거짓이면 죽은 나무들 나이를 2차원 리스트(r*c)에 따로 저장

3. 모든 나무 순회뒤, 흙의 양분을 채워줌(죽은 나무들 나이 /2 포함해서)

4. 모든 나무 순회하며 나이가 5의 배수이면 나이가 1인 나무를 리스트 뒤에 삽입

위와 같이 작성했습니다.

봄여름겨울을 합해서 eat_energy() 가을이 breed_tree()입니다.

어디서 시간초과가 날까요? pypy도 시간초과입니다

도와주세요~!

tree.sort(reverse=True)
r=n
c=len(A[0])
def eat_energy(soil, tree_list, energy_list):
    idx=len(tree_list)-1
    global r,c
    dead_map=[[0 for _ in range(c)]for _ in range(r)]

    for idx in range(len(tree_list)-1,-1,-1):
        x=tree_list[idx][0]-1; y=tree_list[idx][1]-1
        if soil[x][y]>=tree_list[idx][2]: 
            soil[x][y]-=tree_list[idx][2]
            tree_list[idx][2]+=1
        else:
            dead_map[x][y]+=tree_list[idx][2]
            del tree_list[idx]

    for i in range(r):
        for j in range(c):
            soil[i][j]+=(energy_list[i][j] + (dead_map[i][j]//2))

head_x=[-1,-1,-1,0,0,1,1,1]
head_y=[-1,0,1,-1,1,-1,0,1]
def breed_tree(tree_list,r,c):
    for idx in range(len(tree_list)):
        if(tree_list[idx][2]%5==0):
            x=tree_list[idx][0]; y=tree_list[idx][1]
            for i in range(len(head_x)):
                ax=x+head_x[i]; ay=y+head_y[i]
                if(ax>=1 and ay>=1 and ax <=r and ay<= c):
                    tree_list.append([ax,ay,1])

soil=[[5 for _ in range(c)]for _ in range(r)]
year=1
while year<=k:
    eat_energy(soil, tree, A)
    breed_tree(tree,r,c)
    year+=1

print(len(tree))

wjdwofus1004 2년 전 0

죽은 나무들도 1차원 배열로 해보시져~

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

문제

문제

출처

ICPC

코드50줄) 파이썬 시간초과..어디서 나는걸까요?

dlgydms96 3년 전 0

wjdwofus1004 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말