글 읽기 - 시간초과를 어떻게 해결해야할지 모르겠습니다ㅠ

gyyoon4u78 3년 전 0

시간초과 해결하기위해서 다른 글에 있는 deque를 사용해보았습니다. 그런데 해결이 되지 않아 혹시 여기서 어떻게 더 수정해야할 지 질문하고 싶습니다.

from collections import deque

N, M, K = map(int, input().split())
insert_energy = [list(map(int, input().split())) for _ in range(N)]
tree = [[deque() for _ in range(N)] for _ in range(N)]
energy = [[5] * N for _ in range(N)]

for m in range(M):
    x, y, age = map(int, input().split())
    tree[x - 1][y - 1].append(age)

# dead = deque()  # 여름때 양분으로 바뀌면 새로 죽은 나무 확인해야함
                  # -> spring에서 죽으면 바로 양분으로 만들어버리기

# answer = 살아남은 나무의 수 -> spring에서 나무 죽음. summer에서 dead 초기화 fall에서 나무 생성
# cnt를 spring에서 더할게아니라 처음 있던 나무 수를 가지고 4계절 돌면서 + - 하는게 best일듯
cnt = M

'''
봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다.
각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다.
하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다.
만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
'''
def spring():
    global cnt
    for i in range(N):
        for j in range(N):
            x = tree[i][j].popleft()  # 어린나무의 나이
            if x <= energy[i][j]:
                energy[i][j] -= x  # 양분 먹었으면 그만큼 줄어들어야함
                tree[i][j].append(x+1)
            else:
                '''
                여름에는 봄에 죽은 나무가 양분으로 변하게 된다.
                각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.
                '''
                energy[i][j] += x // 2  # 즉시 죽음
                # 여름에서 특정위치에 양분으로 추가되므로 위치+값을 dead에 넣어야함.
                cnt -= 1

'''
가을에는 나무가 번식한다.
번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다.
어떤 칸 (r, c)와 인접한 칸은 (r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1, c+1) 이다. 상도의 땅을 벗어나는 칸에는 나무가 생기지 않는다.
'''
near = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
def fall():
    global cnt
    for i in range(N):
        for j in range(N):
            for k in range(len(tree[i][j])):
                if tree[i][j][k] % 5 == 0:
                    for a, b in near:
                        xi, yi = i + a, j + b
                        if 0 <= xi < N and 0 <= yi < N:
                            tree[xi][yi].appendleft(1)  # 작은 값은 앞으로 넣어야함 -> appendleft
                            cnt += 1

'''
겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다.
각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.
'''
def winter():
    for i in range(N):
        for j in range(N):
            energy[i][j] += insert_energy[i][j]

for k in range(K):
    spring()
    fall()
    winter()
print(cnt)
# cnt를 계속 들고다녀야지 최종 cnt가 나온다. 아니면 계속 리뉴얼됨. cnt

caritas1996 3년 전 1

혹시 테스트케이스는 답이 잘 나오시나요? 의문인 부분이 있습니다. (만약 문제가 없다면 무시하셔도 됩니다)

spring()에서 현존하는 양분(energy[i][j])이 현재 나이(x)보다 적으면 바로 여름에서 이뤄져야 할 연산을 하고 있습니다.

봄에서의 연산이 끝난 후 여름에서의 작업이 이뤄져야 합니다.

energy[i][j]에 (죽은 나무의 나이)/2를 바로 더하지 않고 별도 변수에 담아준 뒤 다음 위치로 넘어가기 직전에 energy[i][j]에 더해줘야 합니다.

fall()과 winter()에서 서로 컨트롤하는 변수에 영향을 주는 연산이 없으므로 합치셔도 됩니다.

~~결과에 유의미한 영향을 끼칠지는 모르겠네요.~~

제가 파이썬을 안써서 ideone에 복붙해서 컴파일을 해보려 했는데 오류가 나서 테스트를 못해봤네요..

도움이 됐으면 좋겠습니다.

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

문제

문제

출처

ICPC

시간초과를 어떻게 해결해야할지 모르겠습니다ㅠ

gyyoon4u78 3년 전 0

caritas1996 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말