1749 - 점수따먹기

info

• 문제 보기: 1749 - 점수따먹기
• 소요 시간: 41분 31초
• 풀이 언어: python
• 체감 난이도: 3️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

누적합

풀이 코드

info

• 메모리: 110972 KB
• 시간: 3064 ms

PyPy3만 통과하는 코드

import sys
from math import inf
input = sys.stdin.readline

n, m = 0, 0
prefix_sum = []

def solution():
    global n, m, prefix_sum
    
    n, m = map(int, input().split())
    prefix_sum = [[0 for _ in range(m+1)] for _ in range(n+1)]
    
    # calculate prefix sum
    for i in range(n):
        data = list(map(int, input().split()))
        for j, k in enumerate(data):
            prefix_sum[i+1][j+1] = prefix_sum[i][j+1] + prefix_sum[i+1][j] - prefix_sum[i][j] + k
            
    # brute force
    mx = -inf
    for y1 in range(1, n+1):
        for x1 in range(1, m+1):
            for y2 in range(y1, n+1):
                for x2 in range(x1, m+1):
                    res = prefix_sum[y2][x2] - prefix_sum[y1-1][x2] - prefix_sum[y2][x1-1] + prefix_sum[y1-1][x1-1]
                    mx = max(mx, res)
    
    print(mx)


if __name__ == '__main__':
    solution()

풀이 해설

완탐은 PyPy만 통과하기 때문에, Python으로 통과하려면 3중 for문으로 최적화해야 한다.

mx = -inf
for y1 in range(1, n+1):
    for x1 in range(1, m+1):
        for y2 in range(y1, n+1):
            for x2 in range(x1, m+1):
                res = prefix_sum[y2][x2] - prefix_sum[y1-1][x2] - prefix_sum[y2][x1-1] + prefix_sum[y1-1][x1-1]
                mx = max(mx, res)

상단의 완탐 로직을 다음과 같이 최적화할 수 있다.

누적합 리스트인 prefix_sum을 순회하는 것이 아니라, arr이라는 원본 행렬을 순회한다.

mx = -inf
for i in range(1, n+1):
    p = [0] * (m+1)
    for j in range(i, n+1):
        t = [0] * (m+1)
        for k in range(1, m+1):
            p[k] += arr[j][k]
            t[k] = max(t[k - 1] + p[k], p[k])
            mx = max(t[k], mx)

메모

• 그나저나 p와 t같은 네이밍은 근원이 뭘까. 누적합에서 나름 자주 보이던데?