알고리즘
백준 1749: 점수따먹기 Python
짱이 되었어
2022. 9. 7. 23:08
https://www.acmicpc.net/problem/1749
1749번: 점수따먹기
동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점
www.acmicpc.net
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로 바꿔서 돌려야겠다.