글 읽기 - 파이썬 dp인데 시간초과가 납니다.

zxaq15 3년 전 0

dp로 풀었고 pypy3으로 채점했는데 3%에섯 시간초과가 나네요;

이유가 뭘가요?

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

dp = [[0]*n for _ in range(n)]

dp[0][0] = board[0][0]
row_tot = col_tot = dp[0][0]
for i in range(1, n):   # dp 첫번째 행과 첫번째 열을 먼저 채워줌
    dp[0][i] = row_tot + board[0][i]
    row_tot += board[0][i]
    dp[i][0] = col_tot + board[i][0]
    col_tot += board[i][0]
    
# 나머지 dp 완성시켜줌
for i in range(1, n):
    for j in range(1, n):
        dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + board[i][j]


for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1

    if x1 == 0 and y1 == 0:
        print(dp[x2][y2])
    elif x1 == 0:
        print(dp[x2][y2]-dp[x1][y1-1])
    elif y1 == 0:
        print(dp[x2][y2]-dp[x1-1][y2])
    else:
        print(dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1])

shg9411 3년 전 0

빠른 입력 사용하시면 틀렸습니다를 받습니다.

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

문제

문제

출처

ICPC

파이썬 dp인데 시간초과가 납니다.

zxaq15 3년 전 0

shg9411 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말