[BOJ][Python]11660번 풀이

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

import sys
ssr = sys.stdin.readline

n,m = map(int, ssr().split())
num = [list(map(int, ssr().split())) for _ in range(n)]
dp = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    dp[i][0] = num[i][0]
    for j in range(1,n):
        dp[i][j] += num[i][j] + dp[i][j-1]
for _ in range(m):
    x1,y1,x2,y2 = map(int, ssr().split())
    ans = 0
    for i in range(x1-1,x2):
        if y1-2 < 0:
            ans += dp[i][y2-1]
        else:
            ans += dp[i][y2-1] - dp[i][y1-2]
    print(ans)

이번 문제는 좀 아슬아슬하게 통과했네요. 데이터양이 조금 더 많으면 시간초과가 날 것 같습니다.

 

문제 접근은 dp와 누적 합입니다. 누적 합 문제는 클래스 4 정도에 오셨다면 한 번 이상은 경험해보셨을 것 같은데요. 이번 문제는 제 입장에서는 처음으로 2차원 배열로 주어진 누적합 문제입니다. 근데 뭐 크게 다를 건 없었습니다. 오히려 혼자서 꼬아서 생각하느라 약간 시간을 낭비했구요. 각 행 별로 따로 누적합을 진행해주면 되었습니다. 그리고 마지막에 반복문으로 조건에 맞는 만큼 더하고 빼주면 됐네요. 인덱스 에러를 방지하기 위해서  y1의 범위를 정해줬습니다(에러가 안나더라도 원하지 않는 값이 되어서 결과가 달라집니다).