https://www.acmicpc.net/problem/1749
공부 날짜 : 2023.01.30
정답 참조 여부 : x
2차원 누적합에서 최대값을 구하는 문제
누적합을 구하고 모든 경우에 대해서 탐색하며 문제를 풀었지만 만족스럽지 않다.
시간복잡도가 O(N^2+M^2)로 시간초과가 나는데 Pypy3로 제출하니 정답으로 나왔기 때문이다.
채점현황을 보니 대부분 Pypy3로 제출된 걸로 보아 비슷비슷하게 푼거 같지만 다른 로직이 있을까 생각이 들었다.
제출자 중에 Python으로 풀고 공개로 해주신분이 계셔서 해당 코드를 참고해서 공부했다.
정답자분의 코드에서는 열의 누적합은 0~n, 1~n, 2~n ... i~n 까지 각각 구해줬고,
행의 누적합은 누적합 과정에서 max를 통해 최대값만 찾도록 해준 코드였다.
아마 옛날이였으면, Pypy3로 정답이 나온뒤에 그냥 제출하고 끝냈을텐데 선배덕분에 정답이더라도 다른사람의 코드를 참고해서 공부하라는 조언덕분에 성장할 수 있었다.
소스코드
import sys
input = sys.stdin.readline
################################################
n, m = map(int, input().split())
data = []
for i in range(n):
data.append(list(map(int, input().split())))
sum_data = [[0 for _ in range(m+1)] for _ in range(n+1)]
# 누적 합 구하기
for i in range(1, n+1):
for j in range(1, m+1):
sum_data[i][j] = sum_data[i][j-1] + data[i-1][j-1] + sum_data[i-1][j] - sum_data[i-1][j-1]
answer = int(-10e9)
for x1 in range(1, n+1):
for y1 in range(1, m+1):
for x2 in range(x1, n+1):
for y2 in range(y1, m+1):
answer = max(answer, sum_data[x2][y2] - sum_data[x1-1][y2] - sum_data[x2][y1-1] + sum_data[x1 - 1][y1 - 1])
print(answer)
