[D2] 2001. 파리 퇴치

2001. 파리 퇴치

 

✏️ 문제 풀이

- 누적합 알고리즘 

 

def calculate_prefix_sum(lst, N):
    # 누적합 배열 초기화
    prefix_sum = [[0] * (N + 1) for _ in range(N + 1)]
    
    # 누적합 계산
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            prefix_sum[i][j] = lst[i - 1][j - 1] + prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1]
    
    return prefix_sum

T = int(input())

for tc in range(1, T + 1):
    N, M = map(int, input().split())
    lst = [list(map(int, input().split())) for _ in range(N)]
    
    # 누적합 계산
    prefix_sum = calculate_prefix_sum(lst, N)
    
    # 최대 합 저장할 변수 초기화
    mx = 0
    
    # MxM 부분 배열의 최대 합 계산
    for i in range(N - M + 1):
        for j in range(N - M + 1):
            # MxM 부분 배열의 합을 누적합을 통해 계산
            total = (prefix_sum[i + M][j + M]
                     - prefix_sum[i][j + M]
                     - prefix_sum[i + M][j]
                     + prefix_sum[i][j])
            mx = max(mx, total)
    
    print(f"#{tc} {mx}")