[BOJ] 구간 합 구하기 5

문제풀러가기!

유명 IT회사의 문제로 이와 비슷한 문제가 수록된 적이 있습니다. 역시 DP였습니다. 그때짠 코드는 완전히 비효율적인 코드를 짰었기 때문에 시간 초과가 났지만, 이번 기회에 풀이법을 알게되었습니다. 저는 구간 합이라는 개념을 아에 모르고 있었습니다. 물론 광고삽입(2021카카오 공채)에서 출제된 문제에도 구간 합과 비슷한 개념이 들어가지만, 그걸 적용을 못했습니다. 생각이 닫혀 있는거 같아요..

결국 문제 풀이 관건은 주어진 배열을 돌면서 (0,0)부터 (x,y)까지의 값을 행렬의 모든 원소에 적용하는 것입니다. 그리고 난 뒤에 구할 부분만 싹 빼면 되기 때문에 쉽게 접근할 수 있는 문제였습니다. 관련된 문제를 몇개 더 풀어봐야겠네요. 이김에 확실히 잡아보죠.

그리고 이 문제도 코틀린 코드로 바꿔서 해봐야겠습니다.

아래는 정답 코드입니다.

import sys

n, m = map(int, input().split())

arr = [[0] * (n + 1)]
for _ in range(n):
    arr.append([0]+list(map(int, sys.stdin.readline().split())))

for i in range(1, n+1):
    for j in range(1, n):
        arr[i][j+1] += arr[i][j]

for j in range(1, n+1):
    for i in range(1, n):
        arr[i+1][j] += arr[i][j]

for _ in range(m):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    print(arr[x2][y2] - arr[x1-1][y2] - arr[x2][y1-1] + arr[x1-1][y1-1])

출처: gramm님의 블로그!