글 읽기 - 시간복잡도를 어떻게 줄여야 할까요

hajin8565 3년 전 0

시간초과에 계속 걸리네요 어떻게든 ac라도 받고싶어 pypy까지 썼는데도 시간초과가 납니다 조언부탁드립니다

import sys
input = sys.stdin.readline
a, b = map(int, input().split())
diamine = [0]*a
for i in range(a):
    diamine[i] = list(input().rstrip())
diaup = [[0 for col in range(b)]for raw in range(a)]
diadown = [[0 for col in range(b)]for raw in range(a)]
biggestsize = int(0)


def upcount(i, j):
    plus = int(1)
    while True:
        if i-plus <= -1 or j + plus >= b:
            break
        elif diamine[i-plus][j+plus] == str(1):
            plus += 1
        else:
            break
    return plus


def downcount(i, j):
    plus = int(1)
    while True:
        if i+plus >= a or j + plus >= b:
            break
        elif diamine[i+plus][j+plus] == str(1):
            plus += 1
        else:
            break
    return plus


for i in range(a):
    for j in range(b):
        if diamine[i][j] == str(1):
            diaup[i][j] = upcount(i, j)
            if diaup [i][j] > biggestsize:
                diadown[i][j] = downcount(i, j)


for i in range(a):
    for j in range(b):
        size = min(diaup[i][j], diadown[i][j])
        if size != 0:
            while size > biggestsize:
                if diadown[i-size+1][j+size-1] >= size and diaup[i+size-1][j+size-1] >= size:
                    biggestsize = size
                    break
                else:
                    size -= 1
print(biggestsize)

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

문제

문제

출처

ICPC

시간복잡도를 어떻게 줄여야 할까요

hajin8565 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말