글 읽기 - 나무재테크 시간초과 질문입니다.

tjdgns9246 4년 전 0

안녕하세요, 나무재테크 관련 시간초과 관련 질문이 있습니다.

나무재테크가 얼마 전에 재채점이 되어서 시간초과 판정을 받았는데요,

어느 부분에서 시간을 많이 뺐기는 지 잘 모르겠네요.

제 추측상으로는 36번째 줄에서 시간을 많이 뺐길 거 같은데, 어떤 자료구조를 써야할까요?

list로는 구현할 수는 없을까요?

고수님들의 답변 기다리겠습니다.

감사합니다.

import sys
from math import floor

inputLine = sys.stdin.readline().split()
n, m, k = int(inputLine[0]), int(inputLine[1]), int(inputLine[2])

field = [[5 for r in range(n + 1)] for c in range(n + 1)]
trees = [[list() for r in range(n + 1)] for c in range(n + 1)]
A = [[0 for r in range(n + 1)] for c in range(n + 1)]

for r in range(1, n + 1):
	inputLine = sys.stdin.readline().split()
	for c in range(1, n + 1):
		A[r][c] = int(inputLine[c - 1])

for i in range(m):
	r, c, age = list(map(int, sys.stdin.readline().split()))
	trees[r][c].append(age)
	trees[r][c] = sorted(trees[r][c])

	
def get_adjacent_tree(row, col):
	adjacent_list = list()
	for dr in (-1, 0, 1):
		for dc in (-1, 0, 1):
			if dr != 0 or dc != 0:
				adjacent_list.append((row + dr, col + dc))
	return adjacent_list


for year in range(k):
	dead_trees = list()
	# spring
	for r in range(1, n + 1):
		for c in range(1, n + 1):
			for i, age in reversed(list(enumerate(trees[r][c]))):
				if field[r][c] >= age:
					field[r][c] -= age
					trees[r][c][i] += 1
				else:
					dead_trees.append((r, c, age))

	# summer
	for r, c, age in dead_trees:
		field[r][c] += floor(age / 2)
		trees[r][c].remove(age)

	# autumn
	for r in range(1, n + 1):
		for c in range(1, n + 1):
			for i, age in enumerate(trees[r][c]):
				if age % 5 == 0:
					for new_r, new_c in get_adjacent_tree(r, c):
						if 1 <= new_r <= n and 1 <= new_c <= n:
							trees[new_r][new_c].append(1)
			# winter
			field[r][c] += A[r][c]

count = 0
for r in range(1, n + 1):
	for c in range(1, n + 1):
		count += len(trees[r][c])
print(count)

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

문제

문제

출처

ICPC

나무재테크 시간초과 질문입니다.

tjdgns9246 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말