백준 1749: 점수따먹기 Python

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

1749번: 점수따먹기

from sys import stdin

N, M = map(int, stdin.readline().split())    # N: 세로, M: 가로
arr = [list(map(int, input().split())) for _ in range(N)]

# 누적합 구하기
sum_arr = [[0] * (M+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, M+1):
        sum_arr[i][j] = arr[i-1][j-1] + sum_arr[i-1][j] + sum_arr[i][j-1] - sum_arr[i-1][j-1]

# 구간합 구하기
max_value = -987654321987654321
for i1 in range(1, N+1):
    for j1 in range(1, M+1):
        for i2 in range(i1, N+1):
            for j2 in range(j1, M+1):
                value = sum_arr[i2][j2] - sum_arr[i1-1][j2] - sum_arr[i2][j1-1] + sum_arr[i1-1][j1-1]
                # max_value = max(max_value, sum_arr[i2][j2] - sum_arr[i1-1][j2] - sum_arr[i2][j1-1] + sum_arr[i1-1][j1-1])
                if value > max_value:
                    max_value = value

print(max_value)

 

누적합과 구간합(Prefix Sum) 알고리즘을 사용했다.

누적합 공식은 

sum_arr[i][j] = arr[i-1][j-1] + sum_arr[i-1][j] + sum_arr[i][j-1] - sum_arr[i-1][j-1]

구간합 공식은

value = sum_arr[i2][j2] - sum_arr[i-1][j2] - sum_arr[i2][j1-1] _ sum_arr[i1-1][j1-1]

이다.

 

 

이 문제는 4중 for문을 쓰기 때문에 python으로 돌렸을 때 계속해서 시간초과가 났는데, pypy로 바꿔서 하니까 바로 통과했다.

편법같긴 하지만 파이썬이 안될 때는 빨리 pypy로 바꿔서 돌려야겠다.