[SWEA-2001][Python] 파리 퇴치

문제

N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개수를 의미한다.
아래는 N=5 의 예이다.

 

M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다.
죽은 파리의 개수를 구하라!
예를 들어 M=2 일 경우 위 예제의 정답은 49마리가 된다.

 

 

제약 사항

1. N 은 5 이상 15 이하이다.
2. M은 2 이상 N 이하이다.
3. 각 영역의 파리 갯수는 30 이하 이다.

 

입력

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고,
다음 N 줄에 걸쳐 N x N 배열이 주어진다.

 

출력

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.
(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

 

예제

[입력]	[출력]
10 5 2 1 3 3 6 7 8 13 9 12 8 4 16 11 12 6 2 4 1 23 2 9 13 4 7 3 6 3 29 21 26 9 5 8 21 19 8 0 21 19 9 24 2 11 4 24 19 29 1 0 21 19 10 29 6 18 4 3 29 11 15 3 3 29 ...	#1 49 #2 159 ...

 

문제 해결 방법

• 4중 for 문을 이용하여 브루트 포스(Brute Force) 방법대로 풀었다.

max_value = 0
for i in range(N - M + 1):
    for j in range(N - M + 1):

        sum_area_values = 0
        for k in range(M):
            for l in range(M):
                sum_area_values += matrix[i + k][j + l]

        if max_value <= sum_area_values:
            max_value = sum_area_values

 

• 범위를 정확하게 확인하여 프로그래밍하는 연습을 할 수 있는 문제였다.
• 2차원 배열 누적합 알고리즘을 이용하여 풀 수도 있다.

2차원 배열 누적합의 예

# 누적합 배열 생성
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] = prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1] + matrix[i - 1][j - 1]

max_value = 0
for i in range(N - M + 1):
    for j in range(N - M + 1):
        # 영역의 누적합 계산
        sum_area_values = prefix_sum[i + M][j + M] - prefix_sum[i][j + M] - prefix_sum[i + M][j] + prefix_sum[i][j]

        if max_value < sum_area_values:
            max_value = sum_area_values

 

코드

T = int(input())

for test_case in range(1, 1 + T):
    N, M = map(int, input().split())

    # 맵 객체를 정수형으로 변환
    N = int(N)
    M = int(M)

    # N x N 리스트를 생성하고 안에 요소 넣기
    matrix = []
    for i in range(N):
        num_list = list(map(int, input().split()))
        matrix.append(num_list)

    # M x M 크기의 영역으로 N x N 리스트 내부를 순회하면서, 해당 영역 안에 있는 값들의 합의 최댓값 구하기
    max_value = 0
    for i in range(N - M + 1):
        for j in range(N - M + 1):

            sum_area_values = 0
            for k in range(M):
                for l in range(M):
                    sum_area_values += matrix[i + k][j + l]
            
            if max_value <= sum_area_values:
                max_value = sum_area_values
    
    print(f"#{test_case} {max_value}")

 

참고

• 난이도 : D2