글 읽기 - 파이썬 시간초과

djfkfk12345 1년 전 1

시간초과가 뜹니다

어떤 방향으로 수정하면 좋을까요..?

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
lst=[]
for _ in range(N):
    lst.append(list(map(int,input().split())))
for i in range(M):
    x1,y1,x2,y2=map(int,input().split())
    x1-=1;x2-=1;y1-=1;y2-=1
    sum=0
    for j in range(x1,x2+1):
        for k in range(y1,y2+1):
            sum=sum+lst[j][k]
    print(sum)

chldn323 1년 전 1

시간 복잡도가 O(M*N*2)인데 M<=100000이기 때문에 N=1024, M=100000이면 너무 오래 걸립니다.

DP(동적 프로그래밍)을 써서 해결해 보세요.

djfkfk12345 1년 전 0

해결했습니다 감사합니다~

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

문제

문제

출처

ICPC

파이썬 시간초과

djfkfk12345 1년 전 1

chldn323 1년 전 1

djfkfk12345 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말