[Python/백준] 1749_점수따먹기 (누적합)

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

<문제 해설>

2차원 누적합을 사용하면 된다. DP랑 비슷하니까 겁낼 필요가 없고 이해만 하면 완전 쉬운 로직이다.
(시간초과 때문에 python3 말고 PyPy3로 제출하자)

2차원 누적합 테이블 만들기

1. 현재 위치의 값 더하기
   board[i-1][j-1]
2. 위쪽 영역의 누적 합 더하기
   dp[i-1][j]
3. 왼쪽 영역의 누적 합 더하기
   dp[i][j-1]
4. 중복된 부분 빼기
   - dp[i-1][j-1]

# 누적 합 구하기
for i in range(1, N + 1):
    for j in range(1, M + 1):
        dp[i][j] = board[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

그럼 이런식으로 DP 테이블을 만들수 있다.

여기서 5를 보자 5는 왼쪽의 2, 위쪽의 0, 자신의 3이 합쳐져서 만들어졌다.

여기서 7을 보자 7은 왼쪽의 0, 위쪽의 2, 자신의 5가 합쳐져서 만들어졌다.

여기서 16을 잘봐야하는데 16은 왼쪽의 7, 위쪽의 5, 자신의 6이 합쳐졌다. 그리고 왼쪽위인 2를 빼줘야한다.

왜냐하면 2가 5에도 들어있고 7에도 들어있어서 중복을 제거해줘야하기 때문이다.

부분합 구하기

만약 우리가 x1, y1, x2, y2 이런 좌표를 가진 값을 구하고 싶다고 하자

result = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]

그럼 다음과 같이 계산하면 된다.

누적합이랑 비슷하다.

 

• dp[x2][y2]: 전체 누적합
• - dp[x1-1][y2]: 위쪽 제외
• - dp[x2][y1-1]: 왼쪽 제외
• + dp[x1-1][y1-1]: 두 번 제외한 교차 부분 복원

그럼이제 중복이 없도록 for문을 돌려주면된다.

이런식으로 4중 반복문으로 x1, y1, x2, y2를 계산하면서 올라가면 절대 겹칠일이 없이 브루트포스로 모든 값을 계산할 수 있다.

<코드>

import sys

# 입력 받기
N, M = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# 누적 합 배열 초기화 (패딩 포함)
dp = [[0] * (M + 1) for _ in range(N + 1)]

# 누적 합 계산
for i in range(1, N + 1):
    for j in range(1, M + 1):
        dp[i][j] = board[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

# 부분합 최대값 찾기
output = -float('inf')
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):
                # (i1, j1) ~ (i2, j2) 부분합
                total = dp[i2][j2] - dp[i1-1][j2] - dp[i2][j1-1] + dp[i1-1][j1-1]
                output = max(output, total)

print(output)