[백준 - Python] 1749. 점수따먹기

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

 

문제 요약

N*M 행렬의 각 칸에 점수를 하나씩 적고

그 행렬의 부분 행렬을 그려 그 안에 적힌 정수의 합을 구했을 때,

정수 합이 최대가 되는 부분 행렬 구하기 ➮ 최대 합을 출력

 

코드

import sys

n, m = map(int, sys.stdin.readline().split())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# 2차원 누적합 배열 초기화
S = [[0] * (m+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, m+1):
        # A 행렬은 정사이즈 행렬로 만들었기 때문에 A[i][j]가 아니라 A[i - 1][j - 1]을 빼준다.
        S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i - 1][j - 1]

max_sum = -float('inf')

# 모든 가능한 부분 행렬 탐색
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):
                total = S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]
                max_sum = max(max_sum, total)

print(max_sum)

 

 

코드 설명

가능한 부분 행렬의 합을 구하기 위해 누적 합을 활용할 수 있다.

 

우선 주어지는 행렬과 동일한 사이즈의 누적합을 저장할 행렬 S를 만든다.

n, m = map(int, sys.stdin.readline().split())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

S = [[0] * (m+1) for _ in range(n+1)]  # 2차원 누적합 배열 초기화

 

누적합 공식을 그대로 활용하면 되는데,

A 행렬을 마지막에 더해서 가장 오른쪽 아래 한 칸의 값을 더해 누적합을 완성해준다.

 

A 행렬은 정사이즈 행렬로 만들었기 때문에 A[i][j]가 아니라 A[i - 1][j - 1]을 빼준다.

for i in range(1, n+1):
    for j in range(1, m+1):
        S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i - 1][j - 1]

 

최댓값 갱신을 위해 음의 무한대로 최대값 변수를 초기화하고

부분 행렬의 네 꼭짓점을 인자로 4중 for문을 돌린다.

 

이때, 누적합 공식을 약간만 변형해서 사용하면 부분 행렬의 합을 빠르게 구할 수 있다.

max_sum = -float('inf')

# 모든 가능한 부분 행렬 탐색
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):
                total = S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]
                max_sum = max(max_sum, total)

 

 

배운 점

- 누적합을 이용하면 2차원 행렬 칸들의 합을 쉽게 구할 수 있다.