글 읽기 - 시간 초과의 벽

onshow1 3년 전 0

다른 블로그 참고하며 시간을 줄여보려고 노력해도 시간 초과의 벽을 넘을 수 가 없습니다.

지금 까지 바꾼 코드로는

1. pop 맨 뒤에서 하기

2. deepcopy -> extend 사용

3. sys 사용

이 있는데 어느 부분을 수정해야 시간 안에 들어올 수 있을지 도움 바랍니다!

감사합니다!!

import sys

input = sys.stdin.readline

n, m, k = map(int, input().split())

a = []
for _ in range(n):
  a.append(list(map(int, input().split())))

trees = []
for _ in range(m):
  x, y, year = map(int, input().split())
  trees.append((year, x, y))

energy = [[5]*(n+1) for _ in range(n+1)]

dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0 ,1]

for _ in range(k):
  r = len(trees)
  trees.sort(reverse=True)
  trees_temp = []
  die_trees = []
  #봄, 가을
  for _ in range(r):
    year, x, y = trees.pop()
    if energy[x][y] < year:
      die_trees.append((year, x, y))
      continue
    else:
      energy[x][y] -= year
      trees_temp.append((year+1, x, y))

      if (year+1) % 5 == 0:
        for i in range(8):
          nx = x + dx[i]
          ny = y + dy[i]

          if nx <= 0 or nx > n or ny <= 0 or ny > n:
            continue
          trees_temp.append((1, nx, ny))
    
  #여름: 봄이랑 같이 처리하면 오류
  for die_tree in die_trees:
    year, x, y = die_tree
    energy[x][y] += (year//2)

  #겨울
  for i in range(1, n+1):
    for j in range(1, n+1):
      energy[i][j] += a[i-1][j-1]
  trees.extend(trees_temp)

print(len(trees))

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

문제

문제

출처

ICPC

시간 초과의 벽

onshow1 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말