백준 11660 파이썬

문제

구간 합 구하기

백준 11660

풀이

간단한 dp 문제이다.

1. 시작지점부터 각 위치에 해당하는 모든 값들을 더하여 저장하는 dp 배열을 만든다.
   ex) 1 2 3 4 의 경우 -> 1 3 6 10 으로
2. 주어진 x2,y2 에서 x1-1,y2 를 빼고 x2,y1-1를 빼고 x1-1,y1-1 을 더해 그 지점에서만 계산하게 한다.
   

import sys
input=sys.stdin.readline
N,M=map(int,input().split())

pyo=[list(map(int,input().split())) for _ in range(N)]

dp=[[pyo[i][j] for j in range(N)]for i in range(N)]
for i in range(1,N):
    dp[0][i]+=dp[0][i-1]
    dp[i][0]+=dp[i-1][0]
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]

for i in range(M):
    x1,y1,x2,y2=map(int,input().split())
    
    ans=dp[x2-1][y2-1]
    if y1-2>=0:
        ans-=dp[x2-1][y1-2]
    if x1-2>=0:
        ans-=dp[x1-2][y2-1]
    if x1-2>=0 and y1-2>=0:
        ans+=dp[x1-2][y1-2]
    print(ans)

첫 번째 시간초과

import sys
input=sys.stdin.readline 

이 부분을 안하면 가끔 python에서는 시간초과가 난다.. 항상 추가 해 줄 것

결과 정답