글 읽기 - 14500 파이썬 시간초과 질문있습니다.

skulter 1년 전 0

해당 코드로 문제를 풀었는데 반례에 답은 맞는데 시간초과가 나옵니다.

제 코드에서 어디를 개선해야 시간초과를 극복할수있을까요?

pypy, pythone3 모두 시간초과가나옵니다.

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]

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

maxValue = 0
result = 0
maxResult = 0


def solution(x, y):
    global visited, maxValue, maxResult
    maxValue = matrix[x][y]
    curVal = 0
    curMat = (0, 0)
    prevMat = []
    for j in range(3):
        if j == 2:
            for prevX, prevY in prevMat:
                for i in range(4):
                    nx = prevX + dx[i]
                    ny = prevY + dy[i]
                    if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                        if curVal < matrix[nx][ny]:
                            curVal = matrix[nx][ny]
                            curMat = (nx, ny)
        else:
            if maxValue + curVal < maxResult:
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                        if curVal < matrix[nx][ny]:
                            curVal = matrix[nx][ny]
                            curMat = (nx, ny)
        x = curMat[0]
        y = curMat[1]
        prevMat.append((x, y))
        visited[x][y] = True
        maxValue += curVal
        curVal = 0
        result = maxValue
    maxResult = max(result, maxResult)
    visited = [[False] * M for _ in range(N)]


for x in range(N):
    for y in range(M):
        visited[x][y] = True
        solution(x, y)

print(maxResult)

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

문제

문제

출처

ICPC

14500 파이썬 시간초과 질문있습니다.

skulter 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말