[백준] 2차원 배열의 합 - 2167번 문제 (Python)

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

2167번: 2차원 배열의 합

---

문제

2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.

입력

첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M).

출력

K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 231-1보다 작거나 같다.

코드 정답

import sys
input = sys.stdin.readline

# 2167
n, m = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*(m+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = li[i-1][j-1] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]

k = int(input())
for _ in range(k):
    i, j, x, y = map(int, input().split())
    print(dp[x][y] - dp[x][j-1] - dp[i-1][y] + dp[i-1][j-1])

풀이

1~2행 : input 대신 sys.stdin.readline 을 사용하여 입출력 속도를 빠르게 만들어주었습니다.

import sys
input = sys.stdin.readline

4~7행 : 띄워쓰기를 기준으로 값 2개를 입력받아 각각 변수 n과 m에 저장합니다. 다음 행에는 정수값을 여러개를 입력받는데 그것을 띄워쓰기를 기준으로 리스트 형태로 만들어 li 에 저장합니다. 이 행위를 n번 반복합니다. 이후 dp 라는 변수를 만들어내는데 용도로는 문제에 해당하는 값을 저장하는 용도로 쓰이게 됩니다.

# 2167
n, m = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*(m+1) for _ in range(n+1)]

9~11행 : n번 10~11행을 반복하고 m번 11행을 반복하게 됩니다. dp[1][1] 부터 dp[n][m]까지 계산된 결과들이 저장이 되며 이 리스트에는 li 에 입력한 값에 따라 문제에서 요구할 답들이 저장되게 됩니다.

for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = li[i-1][j-1] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]

13~16행 : 정수 하나를 입력받아 k에 저장한 후 15~16행을 k번 반복합니다. 반복이 될 때마다 정수 4개를 띄워쓰기를 기준으로 입력받아 각각 i, j, x, y에 저장하게 됩니다. 이후 입력한 값들을 토대로 값을 계산하여 계산된 값을 출력합니다.

k = int(input())
for _ in range(k):
    i, j, x, y = map(int, input().split())
    print(dp[x][y] - dp[x][j-1] - dp[i-1][y] + dp[i-1][j-1])