글 읽기 - [파이썬] 시간초과

care9000 4년 전 0

시간 초과 관리 어떻게 하나요 ㅠㅠ 고수님들 도와주세요 ㅠ

import sys
sys.stdin = open('16235_나무_재테크.txt')

import collections

def bubble_sorted():
    for i in range(len(Tree_location) - 1):
        for j in range(i + 1, len(Tree_location)):
            if Tree_location[i][2] > Tree_location[j][2]:
                Tree_location[i], Tree_location[j] = Tree_location[j], Tree_location[i]


def spring():
    for Tree in Tree_location:
        if land[Tree[0]][Tree[1]] >= Tree[2]:
            land[Tree[0]][Tree[1]] -= Tree[2]
            Tree[2] += 1
        else:
            Tree[2] += 100

def summer():
    # 죽은 나무가 양분변하고 제거시킴
    for Tree in Tree_location:
        if Tree[2] >= 100:
            land[Tree[0]][Tree[1]] += (Tree[2] % 100) // 2
            Tree[2] = -1

    bubble_sorted()
    cnt = 0
    for Tree in Tree_location:
        if Tree[2] == -1:
            cnt += 1
        else:
            break
    for i in range(cnt):
        Tree_location.popleft()

def fall():
    q = []
    for Tree in Tree_location:
        if Tree[2] % 5 == 0:
            for k in range(8):
                i_tem = Tree[0] + dx[k]
                j_tem = Tree[1] + dy[k]
                if ispass(i_tem, j_tem):
                    q.append([i_tem, j_tem, 1])
    for new in q:
        Tree_location.appendleft(new)

def winter():
    for i in range(N):
        for j in range(N):
            land[i][j] += supply_info[i][j]

def ispass(i, j):
    if -1 < i < N and -1 < j < N:
        return True
    return False

#좌상, 상, 우상, 좌, 우, 좌하, 하, 우하
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]



N, M, K = map(int, input().split())
land = [[5 for _ in range(N)] for _ in range(N)]
supply_info = [list(map(int, input().split())) for _ in range(N)]
# 공급 량 정하기


dummy_list = [list(map(int, input().split())) for _ in range(M)]

Tree_map = [[0 for _ in range(N)] for _ in range(N)]
Tree_location = collections.deque([])
for dummy in dummy_list:
    Tree_map[dummy[0] - 1][dummy[1] - 1] = dummy[2]
    Tree_location.append([dummy[0] - 1, dummy[1] - 1, dummy[2]])



for year in range(K):
    if len(Tree_location):
        spring()
        summer()

        fall()
        winter()
    else:
        break


print(len(Tree_location))

cynicaldummy 3년 전 0

음 저도 deque를 써서 처음 수행을 했을때 시간초과가 나오더라고요...

dictionary를 활용해서 해결했습니다... 중복되는 나무의 나이가 많아지는 경우 일일이 하나씩 처리하다 보니 오래걸려서 시간초과가 나오는것 같습니다.

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

문제

문제

출처

ICPC

[파이썬] 시간초과

care9000 4년 전 0

cynicaldummy 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말