[Python] BOJ 1749 - 점수따먹기

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

1749번: 점수따먹기

# 일차원 배열 상에서의 누적합이 아닌 2차원 배열에서의 누적합을 구해 푸는 문제이다.

 

# 우선 누적합 배열을 만들어야 하는데, 누적합을 일일이 반복문을 돌며 구하면

   "가로 x 세로"(0 < 가로 <= M, 0 < 세로 <= N)를 (N x M)칸 채워야 하므로 

   시간복잡도는 O(N^2 x M^2) = O(16억)이 되서 시간초과가 날 것이다.

 

# 따라서 일차원 배열에서 누적합을 구하는 것 처럼 이전에 구한 누적합을 이용해

   다음 항도 구하는 식으로 prefix_sum배열을 채워주었다.

 

 

# 위 그림에서 I까지의 누적합 (A+B+C+...+H+I)는

   (A+B+C+D+E+F) + (A+B+D+E+G+H) - (A+B+D+E) + I 로 구할 수 있다.

    * 여기서 (A+B+C+D+E+F)는 F까지의 누적합, (A+B+D+E+G+H)는 H까지의 누적합,

        (A+B+D+E)는 E까지의 누적합, I는 I에 해당하는 nums값이다.

 

  따라서, 이전에 구한 prefix_sum(누적합)값은 O(1)에 불러올 수 있고, I에 해당하는 값만 반복문을 돌며

  구하면 O(N x M)에 누적합을 구할 수 있다!

 

# 계산을 편하게 하기 위해 맨 위와 맨 왼쪽에 0을 추가시켜주고

   x1, y1, x2, y2를 1부터 N, M까지 증가시켜가며 4중 for문으로 완전탐색을 돌려주며 

   부분행렬안에 들어 있는 정수값의 합을 구해준다. 그 합이 ans보다 크면 갱신해준다.

 

# 부분행렬 안에 있는 정수들의 합을 구하는 것도 누적합을 구하는 것과 비슷하다.

   위의 그림에서 (E+F+H+I)를 구하고 싶으면 I까지의 누적합(A+B+C+...+H+I)에서

   C까지의 누적합(A+B+C)과 G까지의 누적합(A+D+G)을 빼 준 뒤

   겹치는 부분인 A를 더해주면 된다.

 

import sys
input = sys.stdin.readline
N, M = map(int,input().split())
nums = [list(map(int,input().split())) for _ in range(N)]

# 일반식을 통한 prefix_sum 채우기
prefix_sum = [[0] * (M+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, M+1):
        prefix_sum[i][j] = prefix_sum[i - 1][j] + prefix_sum[i][j - 1] + nums[i - 1][j - 1] - prefix_sum[i - 1][j - 1]

# ans의 최솟값은 200x200칸에 모두 -10000이 들어 있는 경우인 -4억이다
# x1, y1, x2, y2를 증가시켜가며 4중 for문으로 완전탐색
# 부분행렬 구하는 것도 공식을 통해..
ans = -400000001
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):
                ans = max(ans, prefix_sum[x2][y2] - prefix_sum[x2][y1 - 1] - prefix_sum[x1 - 1][y2] + prefix_sum[x1 - 1][y1 - 1])
print(ans)

(solved.ac 티어: 골드 4)