SWEA 2001 파리 퇴치 (핵심 : i+x, j+y)

💡문제 분석 요약

• N*N 파리 box에서 파리를 딱 내리치면 M*M만큼의 칸을 내리칠 수 있어서 해당 칸의 파리를 잡을 수 있다.
• 이때, 잡을 수 있는 파리의 최대 수를 구한다.

💡알고리즘 설계

• 보자마자 4중 for문은 아닐거고 ...... 라고 시작했는데 결국 다른 풀이를 생각해내진 못했다.
• 물론 4중 for문이 될 것이라는 확신은 있었다. N의 크기가 15고, M의 크기는 2~N 이었기 때문에 최대 O(225)일 것이라고 생각해서 될 거라고 봤는데 사실 크기가 커지면 쓸모 없는 코드니까 .... 4중 for문은 피하려고 했다.
• 사실 M*M 박스는 움직이면서 이전과 겹치는 부분이 있으니까 그 부분만 빼고 나머지 새로운 열 혹은 행에 대해서 더해주면 더 효율적일 것이라고 생각했는데 코드를 생각해내진 못했다.

💡코드

T = int(input())
for test_case in range(T):
    # N은 5~15 , M은 2~N
    n, m = map(int, input().split()) # N*N 배열, m*m크기로 파리채 블로킹
    maps = [] # 영역 1개에 최대 파리는 30마리
    for _ in range(n):
        maps.append(list(map(int, input().split())))
    
    # 파리채 블로킹 시작
    kill_paris = 0 # 죽인 파리 최대 수
    for i in range(n-m+1):
        for j in range(n-m+1):
            comp = 0
            for x in range(m):
                for y in range(m):
                    comp += maps[i+x][j+y] # 해당 map의 위치에서 x만큼 이동, y만큼 이동하는 것을 의미함.
            kill_paris = max(kill_paris, comp)

    print(f"#{test_case+1}", kill_paris)

💡시간복잡도

• 전체 box에 대한 이중 for문 : (n-m+1) x (n-m+1) 만큼 반복된다.
• 안쪽에서 M*M에 대한 for문 : M*M만큼 반복
• 따라서 전체 시간 복잡도는 O(N^2 * M^2)

💡 틀린 이유, 수정

• 처음 생각은, N*N개 파리 맵에서 m*m개씩 비교하면 된다고 생각했다. 근데 이렇게 하면 N*N의 행렬을 탐색하는데 이중포문, 그 안에서 M*M개로 파리 퇴치 합을 구하는데 또 이중포문이라 사중포문이 될 것 같아서 시도하지 않았다.
• 그리고 M*M 부분을 처리할 때 i+x, j+y를 생각은 해놓고 코드로 표현할 줄 몰라서 틀렸다. 해당 부분은 결국 맵의 i, j 위치에서 x만큼 이동하고, y만큼 이동한다는 것을 의미한다. 그리고 이 x, y의 범위는 m이다.

💡 느낀점 or 기억할정보

• for문 내에서 특정 구역을 탐색해야될 때 i+x, j+y라는 기법을 기억해두기.