코드
from typing import List
# 죽은 파리의 개수를 구하는 함수
def solve(graph: List[List[int]], n: int, m: int) -> int:
result = 0 # 죽은 파리의 최대값을 담은 변수
# 2중 for문 반복문으로 주어진 그래프 탐색
for x in range(n-m+1):
for y in range(n-m+1):
dead_bug_cnt = sum([sum(graph[z][y:y+m]) for z in range(x, x+m)])
result = max(result, dead_bug_cnt)
return result
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
n, m = map(int, input().split()) # 각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고,
graph = [list(map(int, input().split())) for _ in range(n)] # 다음 N 줄에 걸쳐 N x N 배열이 주어진다.
print(f'#{test_case} {solve(graph, n, m)}') # 출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.결과
ChatGPT Code
# 테스트 케이스 수 입력
T = int(input())
# 테스트 케이스 반복
for test_case in range(1, T+1):
# 입력 받기
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
# 최대 파리 수
max_flies = 0
# 파리채 이동
for i in range(n-m+1):
for j in range(n-m+1):
# 파리 수 총합 계산
sum_flies = sum([sum(arr[x][j:j+m]) for x in range(i, i+m)])
# 최대 파리 수 갱신
if sum_flies > max_flies:
max_flies = sum_flies
# 출력
print(f"#{test_case} {max_flies}")ChatGPT 문제풀이
위 코드는 각 테스트 케이스마다 다음과 같은 작업을 수행합니다.
입력 받기: n, m, n x n 크기의 배열 arr
최대 파리 수(max_flies)를 0으로 초기화
파리채 이동: i와 j를 각각 0부터 n-m까지 반복하면서 파리채를 이동시키는 것으로 간주
이동한 위치에서 M x M 범위 내의 파리 수 합(sum_flies) 계산
최대 파리 수(max_flies)와 현재 파리 수(sum_flies)를 비교하여 갱신
테스트 케이스 번호와 최대 파리 수 출력
각 테스트 케이스마다 시간 복잡도는 O(n^2 x m^2)으로, 최악의 경우 T x n^4 x m^2의 시간 복잡도를 가집니다. 하지만 제약 사항에서 주어진 입력 크기를 고려해보면, 실제로는 꽤 빠르게 동작할 것입니다.
문제출처 & 깃허브
