[SWEA] 파리퇴치(2001) - Python(리스트 구현)

2차원 배열의 수들을 입력받아, N크기의 정사각형의 최대값을 출력하는 문제이다.

 

SW Expert Academy

---

테스트 케이스

 

[TC1]

입력 :

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

출력 : 49

해설 : 13 + 9 + 16 + 11 = 49

 

[TC2]

입력 :

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

출력 : 159

 

---

해결 과정

파리채의 잡는 파리의 합을 저장할 공간의 크기를 N - M + 1로 정하고, 거기에 잡은 파리의 수를 저장한다. 그렇게 하면 2차원 배열에서 가장 큰 값을 고르면 된다.

 

---

코드

T = int(input())

for test_case in range(1, T + 1):
    N, M = map(int, input().split())
    map_ = [] #
    result_map = [[0] * (N - M + 1) for _ in range(N - M + 1)]

    for i in range(N):
        map_.append(list(map(int, input().split())))

    for y in range(N - M + 1):
        for x in range(N - M + 1):
            temp = 0
            for z in range(y, y + M):
                temp += sum(map_[z][x : x + M])
            result_map[y][x] = temp # 구한 총합을 저장

    result = max(map(max, result_map))
    print(f'#{test_case} {result}')

 

주석 처리

T = int(input()) # TC 받음

for test_case in range(1, T + 1): # TC 동안
    N, M = map(int, input().split()) # 각각 N, M 받음
    map_ = [] # 파리의 수를 저장할 공간
    result_map = [[0] * (N - M + 1) for _ in range(N - M + 1)] # 파리채로 잡은 파리의 합을 저장할 공간

    for i in range(N): # N동안
        map_.append(list(map(int, input().split()))) # 파리를 저장

    for y in range(N - M + 1): # y축으로 파리채가 움직이는 동안
        for x in range(N - M + 1): # ㅌ축으로 파리채가 움직이는 동안
            temp = 0 # 파리채의 총합을 저장할 변수
            for z in range(y, y + M): # 파리채를 한칸씩 내림
                temp += sum(map_[z][x : x + M]) # 파리채의 한 줄의 합을 총합에 더함
            result_map[y][x] = temp # 구한 총합을 저장

    result = max(map(max, result_map)) # result_map의 한 줄씩 받아 최댓값 구하고, 구한 것 중 최대값 다시 고름
    print(f'#{test_case} {result}')