[BOJ] 11660 구간 합 구하기 5 - python

11660번: 구간 합 구하기 5

11660번: 구간 합 구하기 5

풀이

계산이 최대 100,000번까지이기 때문에 다 계산하는건 사실상 불가 그렇다면 dp테이블을 이용해보자 00부터 특정 칸까지의 구간합을 이용할건데, 계산하는 범위가 맨 첫 줄부터가 아님 → 한 row단위로 끊어서 빼서 계산하자 00을 포함할 때, 한 칸 일 때의 예외 처리

import sys
def input():
    return sys.stdin.readline().rstrip()

N, M = map(int,input().split(" "))
maps = [list(map(int,input().split(" "))) for _ in range(N)]
toCal = [list(map(int,input().split(" "))) for _ in range(M)]

# (0,0)부터 (N,N)까지의 합을 구해놓기
dp = [[0 for _ in range(N)]  for _ in range(N)]
dp[0][0] = maps[0][0]

for r in range(N):
    for c in range(N):
        if c == 0:
            dp[r][c] = dp[r-1][N-1] + maps[r][c]
        else:
            dp[r][c] = dp[r][c-1] + maps[r][c]

def calculate(cal):
    a,b,c,d = cal
    a -= 1 #00시작으로 맞추기
    b -= 1
    c -= 1
    d -= 1
    if a==c and b==d:
        return maps[a][b]
    sum = 0
    for row in range(a,c+1):
        if b == 0:
            sum += dp[row][d]
            if row != 0:
                sum -= dp[row-1][N-1]
        else:
            sum += dp[row][d] - dp[row][b-1]
    return sum

for cal in toCal:
    print(calculate(cal))

얻어가는 것

느낀점

"211113"

소요 시간 : 1h