2117. [모의 SW 역량테스트] 홈 방범 서비스

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu&categoryId=AV5V61LqAf8DFAWu&categoryType=CODE&problemTitle=%EB%B0%A9%EB%B2%94&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

T = int(input())
for tc in range(1, T + 1):
    n, m = map(int, input().split())
    city = [list(map(int, input().split())) for _ in range(n)]
    homes = []
 
    for i in range(n):
        for j in range(n):
            if city[i][j]:
                homes.append((i, j))
 
    for k in range(n + 2, 0, -1):  # 마름모 한 변의 길이(큰 서비스 영역부터 줄여나감)
        cost = k * k + (k - 1) * (k - 1)
        if len(homes) * m >= cost:  # 손해를 보지 않을 때(등호주의)
            max_home_cnt = 0 
            for i in range(n):
                for j in range(n):
                    home_cnt = 0
                    for hi, hj in homes:  # 마름모안에 집이 있는가?
                        if abs(j - hj) + abs(i - hi) < k:  # 마름모 안과 집의 거리
                            home_cnt += 1
                    if home_cnt * m >= cost and max_home_cnt < home_cnt:  # 운영비용<= 수익, 기존보다 더 서비스 가능한 집 수가 많다면
                        max_home_cnt = home_cnt  # 집 수 최댓값 갱신
            if max_home_cnt:  # 집 수 최댓값이 갱신됐으면
                break
 
    print(f'#{tc} {max_home_cnt}')

전체를 담는 큰 마름모부터 시작해서 점점 줄여나가기