https://www.acmicpc.net/problem/2167
Solution
할 때마다 for 문을 행렬로 두 번 돌려 sum을 구하는 방식은 시간 초과가 난다. O(n^2)이기 때문.
1행 1열부터 x행 y열까지의 sum을 한 번에 구해놓고 sum_matrix 리스트에 저장한 뒤 더하기와 빼기로 구하는 방법을 활용한다.
메인 식은 다음과 같다.
print(sum_matrix[x-1][y-1] - sum_matrix[i-2][y-1] - sum_matrix[x-1][j-2] + sum_matrix[i-2][j-2])
if문으로 리스트 범위를 벗어날 경우(i-2, j-2) 예외 처리만 확실하게 해준다.
Python Code
import copy
N, M = map(int, input().split())
#원래 매트릭스 받기
matrix = []
for _ in range(N):
matrix.append(list(map(int, input().split())))
#i, j까지 sum한 매트릭스 따로 만들어주기
sum_matrix = copy.deepcopy(matrix)
for i in range(N):
for j in range(M):
if i == 0 and j == 0:
pass
elif i == 0:
sum_matrix[0][j] += sum_matrix[0][j-1]
elif j == 0:
sum_matrix[i][0] += sum_matrix[i-1][0]
else:
sum_matrix[i][j] += sum_matrix[i-1][j]
for col in range(j):
sum_matrix[i][j] += matrix[i][col]
K = int(input())
#예외 처리(i-2, j-2가 안되는 경우) 해주고 정답 출력
for _ in range(K):
i, j, x, y = map(int, input().split())
if i == 1 and j == 1:
print(sum_matrix[x-1][y-1])
elif i == 1:
print(sum_matrix[x-1][y-1] - sum_matrix[x-1][j-2])
elif j == 1:
print(sum_matrix[x-1][y-1] - sum_matrix[i-2][y-1])
else:
print(sum_matrix[x-1][y-1] - sum_matrix[i-2][y-1] - sum_matrix[x-1][j-2] + sum_matrix[i-2][j-2])
'Programming [Python] > 백준 알고리즘 솔루션' 카테고리의 다른 글
#254 백준 파이썬 [15655] N과 M (6) - 조합 (0) | 2019.12.04 |
---|---|
#253 백준 파이썬 [10996] 별 찍기 - 21 (0) | 2019.12.04 |
#251 백준 파이썬 [13420] 사칙연산 (0) | 2019.12.03 |
#250 백준 파이썬 [15654] N과 M (5) - 순열 (0) | 2019.12.03 |
#249 백준 파이썬 [16194] 카드 구매하기 2 (0) | 2019.12.03 |