[SWEA]2001. 파라 퇴치

2005. 파리 퇴치

문제설명

N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개수를 의미합니다.

아래는 N = 5의 예입니다.

M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 합니다.

예를 들어 M =2 일 경우 위 예제의 정답은 49마리 입니다.

제약 사항

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

생각해보기

M x M이라고 치면, (0,0)부터 시작했을 때, (0, 0)(0, 1)(1, 0)(1, 1)이렇게 네칸 부터 시작해서 한 칸씩 옆으로 옮기면서 값들을 더해 비교해봐야한다.

(0,1)(0, 2)(1, 1)(1, 2)

T = int(input())
for i in range(1, T+1):
    n, m = map(int, input().split())
    space = []
    for _ in range(n):
        a = list(map(int, input().split()))
        space.append(a)
    hap = 0
    for j in range(n - m-1):  #01
        for k in range(n-m-1):  ##m x m 01
            temp = 0
      
            for l in range(j, j+m): #0,2 > 0,1
                for o in range(k, k+m): #0,2 > 0, 1  
                    temp += space[l][o]
                    if temp > hap:
                        hap = temp
    print(f'#{i} {hap}')

여기서 spce가 완성되고 j의 범위는 5 -2 -1 = 2 그러면 0, 1 k도 0, 1

테스트 케이스의 첫 예로

1
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 를 입력할 때,

n = 5 m =2

T = int(input())
for test_case in (1, T+1):
    n, m = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]

    max = 0
    #파리채를 내려칠 곳 탐색
    for i in range(n-m+1):
        for j in range(n-m+1):
            hap = 0
            #해당 위치를 타격했을 때 잡을 수 있는 파리의 수
            for k in range(m):
                for l in range(m):
                    hap += arr[i+k][j + l]
                    if hap > max:
                        max = hap

    print(f'#{test_case} {max}')
    

알음알음 성장로그:티스토리

핵심 정리

#N X M의 배열 탐색
for i in range(N):
    for j in range(M):
        arr[i][j]

• range(n-m+1): 파리채를 휘두를 수 있는 공간

  m의 크기가 1인경우, 모든 배열 공간을 대상으로 탐색할 수 있습니다. m의 크기가 커질 수록 탐색할 수 있는 횟수도 줄어듦니다.

  • n 이 5이고 m이 1일때 탐색할 수 있는 공간 수 = 25
  • m = 2이면 16개
  • m = 3이면 9개

---

아직까지 뭔가 이차원 배열에 대해서 정확하게 그려지지 않습니다..ㅠㅠㅠ

더 많이 보고 익숙해져야겠습니다.