코테분석#9-3 이차원 배열의 합 (백준 2167)

1. 문제

2. 나의 풀이

3. 쌤's 풀이

• 파이썬은 느려서 순차적으로 풀면 시간초과남!
• 아래와 같이 부분합을 이용해야함!
  
• 이런 유형의 문제는 거저 주는 문제라고 생각하고 꼭 맞아야함!
• 자주나오는 문제유형이라고 함

1차원 배열의 누적합

# 아래와 같이 값들의 합을 미리 구하는 것을 누적합이라고 함
# 시간복잡도를 줄이기 위해서!
A = [i for i in range(10)]
print(A)
for i in range(1, 10):
    A[i] = A[i-1] + A[i]

print(A)

# DP[i] = i까지 합
# i부터 j까지의 합은 DP[i] - DP[j-1]

문제풀이

N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
# DP[i][j] = 1, 1부터 (i,j)까지의 부분 합
DP = [[0 for i in range(M+1)] for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, M+1):
        DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + A[i-1][j-1]


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

4. 느낀 점