[Python] SW Expert Academy #2117 홈 방범 서비스

📚문제: #2117 홈 방범 서비스(모의 SW 역량테스트)

전체 코드

# 2117 홈 방범 서비스

# K값에 따른 서비스 영억
def SERVICE_AREA(CENTER, K):
    
    # 중심 좌표
    r, c = CENTER
    
    # 서비스 영역
    COVERAGE = []
    
    R = K - 1
    
    # 서비스 영역
    for i in range(1, 2*K):
        
        cur_r = r - (K-i)
        
        COVERAGE.append((cur_r, c))
        
        if i <= K:
            
            for p in range(1, i):
                
                COVERAGE.append((cur_r, c + p))
                COVERAGE.append((cur_r, c - p))
        
        elif i > K:
            
            for p in range(1, R):
                
                COVERAGE.append((cur_r, c + p))
                COVERAGE.append((cur_r, c - p))
                
            R -= 1
        
    return COVERAGE

# 홈 방범 서비스
# Brute Force Algorithm
def HOME_SEC_SERVICE(n, m, G, t):
    
    # 서비스를 제공받는 집들의 최대 수, 초기화    
    MAX_SERVICE_PROVIDED = -1

    # 모든 좌표에 대해서
    for i in range(n):
        
        for j in range(n):
            
            for pair in SERVICE_COST:
                
                K, cost = pair
                
                cnt = 0
                
                if cost <= MAX_BENEFIT:
                    
                    area = SERVICE_AREA([i,j], K)
                    
                    for coord in area:
                        
                        r, c = coord
                        
                        # 주어진 범위를 벗어나지 않을 때
                        if 0 <= r <= n-1 and 0 <= c <= n-1:
                            
                            if G[r][c] == 1:
                                
                                cnt += 1
                
                    # 얻는 수익
                    benefit = cnt * m
                    
                    # 수익이 서비스 투자 비용보다 클 때, 서비스 하는 집의 수 갱신
                    if benefit - cost >= 0:
                        
                        MAX_SERVICE_PROVIDED = max(MAX_SERVICE_PROVIDED, cnt)
                
                # 더 이상 진행할 필요 없는 케이스
                else:
                    
                    break 

    # 답안 출력
    print("#{} {}".format(t, MAX_SERVICE_PROVIDED))
    
# 총 테스트 케이스 T
T = int(input())

# T개의 테스트 케이스
for t in range(1, T+1):
    
    # 도시의 크기 N, 집이 지불할 수 있는 비용 M
    N, M = map(int, input().split())
    
    # 도시
    city = []
    
    # 도시 정보가 주어진다. 1은 집이 위치, 나머지는 0
    for _ in range(N):
        
        city.append(list(map(int, input().split())))
    
    # 집을 찾는다.
    home_cnt = 0
    
    for i in range(N):
        
        for j in range(N):
            
            if city[i][j] == 1:
                
                home_cnt += 1
    
    # 모든 집에 서비스하면 얻는 수입
    MAX_BENEFIT = home_cnt * M
    
    # K에 따른 홈 방범 서비스 비용
    SERVICE_COST = []
    k = 1
    
    while True:

        cal = k**2 + (k-1)**2
        
        if cal < 10 * 20 * 20:
            
            SERVICE_COST.append((k, cal))
        
        else:
            
            break
        
        k += 1
        
    # 함수 실행
    HOME_SEC_SERVICE(N, M, city, t)

TIL

Brute Force + Simulation 문제, 시간 단축을 위해 K값에 따른 서비스 비용이 최대 수익(모든 집을 서비스하였을 때 수익)을 넘어가면 스킵한다. K값에 따른 서비스 비용이 최대 수익보다 작을 때는 알고리즘을 실행하고 서비스 하는 집의 수에 따른 수익을 계산한다. 수익이 더 클 때만 집의 개수를 갱신한다.