짱이 될거야
백준 1749: 점수따먹기 Python 본문
https://www.acmicpc.net/problem/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로 바꿔서 돌려야겠다.
'알고리즘' 카테고리의 다른 글
백준 11650: 좌표 정렬하기 Python (0) | 2022.09.16 |
---|---|
백준 1018: 체스판 다시 칠하기 Python (Brute Force) (0) | 2022.09.15 |
백준 22864: 피로도 Python (0) | 2022.09.13 |
Prefix Sum(구간합), 누적합 (0) | 2022.09.07 |
백준 25083번: 새싹 Python (0) | 2022.07.20 |
Comments