swea2117.홈 방범 서비스

SW Expert Academy

T=int(input())
for tc in range(1,T+1):
    N,M=map(int,input().split())
    arr=[list(map(int,input().split())) for _ in range(N)]
    cost = [0]+[K*K+(K-1)*(K-1) for K in range(1,40)] #cost의 비용을 미리 구하기! (운영영역(K)별 운영 비용)

    def homesafer():
        home =[] #집 좌표 넣어 줄 리스트
        ans = 0 # 답 넣어줄 변수

        #집 좌표 구하기
        for i in range(N):
            for j in range(N):
                if arr[i][j] == 1:
                    home.append((i,j))


        for sy in range(N):
            for sx in range(N):
                box=[0]*40

                for cy,cx in home: #현재 좌표(집)
                    distance=abs(sy-cy)+abs(sx-cx)+1 #집과 운영거리 중심과의 거리(자신 포함해서+1)
                    box[distance] +=1 #거리별로 집 있는 수 추가 (거리를 저장)

                for i in range(1,40):
                    box[i]+=box[i-1] #누적합으로  구해주기

                for j in range(1,40):
                    if cost[j] <=box[j]*M and ans <box[j]: #손해x[비용<=수익(집수*지불비용)],수익 최대 갱신
                        ans = box[j]
        return ans #최대 수익 갱신해 리턴

    ret = homesafer()
    print(f'#{tc} {ret}')

풀이방법

사실 문제 자체가 처음에는 좀 이해가 안되어서 힘들었다. 그래서 설계도 잘 안세워져서 결국 문풀 강의를 통해 겨우 이해하고 디버깅했다. 코드의 전략은 다음과 같다.

1. 운영영역의 비용을 미리 구해서 리스트에 넣어준다.

2. 집의 좌표를 모두 찾아 리스트에 넣어준다.

3. for문을 통해 현재 집 좌표와 서비스영역의중심(sy,sx)의 거리를 절대값을 통해 거리를 찾는다. (이때 자신을 포함해야하므로 +1할 것)

4. 중심과의 거리를 인덱스로 삼아 DAT로 box의 해당 인덱스 값 +=1해 갱신해 준다.

5. 누적합을 통해 (왜? K의 영역이 만약 3이라면 K가 2인것도 포함해야하므로) box의 값을 갱신해 준다.

6. 이제 손해를 안보기 위한 조건 (비용 <= 수익(집의 수 * 지불 비용))과 ans에 수익 최대를 갱신하여

7. 최종적으로 최대 수익을 리턴하게 한다.