[Python] SWEA 2117 홈 방범 서비스

SW Expert Academy

<시행착오 1>

def operation_expense(k):
    return k * k + (k - 1) * (k - 1)
 
for tc in range(int(input())):
    N, M = map(int, input().split())
    homes = [list(map(int, input().split())) for _ in range(N)]
 
    result = 0
    for n in range(N + 2, -1, -1):
        cur_max_result = 0
        for y in range(N):
            for x in range(N):
                visited = [[0 for _ in range(N)] for _ in range(N)]
                cur_result = 0
                for n_y in range(-n+1, n):
                    cur_y = y + n_y
                    diff = abs(abs(n_y) - n)
                    for n_x in range(-diff+1, diff):
                        cur_x = x + n_x
                        if -1 < cur_y < N and -1 < cur_x < N:
                            visited[cur_y][cur_x] = 1
                            if homes[cur_y][cur_x] == 1:
                                cur_result += 1
                if cur_result > cur_max_result:
                    cur_max_result = cur_result
        if cur_max_result * M - operation_expense(n) > 0:
            result = cur_max_result
            break
 
    print('#{} {}'.format(tc + 1, result))

<기본 아이디어>

• 서비스 영역의 크기 k를 정하고 중심 좌표를 움직이면서 영역 전체를 탐색하면서 집을 찾아내는 방식.

<고찰>

• Pass하고 나서 보니깐 참 문제가 많은 코드다. 무려 5중 반복문;;; 접근 방법을 애초에 다르게 해야 함을 느꼈다.

 

<시행착오 2>

def operation_expense(k):
    return k * k + (k - 1) * (k - 1)
 
for tc in range(int(input())):
    N, M = map(int, input().split())
 
    field = [list(map(int, input().split())) for _ in range(N)]
    homes = []
 
    for y in range(N):
        for x in range(N):
            if field[y][x]:
                homes.append((y, x))
 
    max_profit = len(homes) * M
 
    for k in range(N + 2, 0, -1):
        cur_expense = operation_expense(k)
        # 애초에 모든 집을 다 합치더라도 비용을 감당할 수 없을 때 연산하지 않는다.
        if max_profit - cur_expense > 0:
            num_max_home = 0
            for y in range(N):
                for x in range(N):
                    num_home = 0
                    for h_y, h_x in homes:
                        if abs(y - h_y) + abs(x - h_x) < k:
                            num_home += 1
                    if num_max_home < num_home and num_home * M > cur_expense:
                        num_max_home = num_home
            if num_max_home:
                break
 
    print('#{} {}'.format(tc + 1, num_max_home))

<기본 아이디어>

• 서비스 영역의 크기 k를 정하고 중심 좌표를 움직이는 것 까지는 똑같다.
• 미리 집들의 좌표를 리스트에 저장해놓는다.
• 마름모 안에 드는 조건을 나타내는 수식(abs(y - h_y) + abs(x - h_x) < k) 을 만족할 때 서비스 가능한 집이므로 서비스를 제공받는 집의 수를 하나 씩 센다.
• 서비스를 제공받는 집에서 얻을 수 있는 돈이 비용보다 크다면 집의 수를 저장하고 반복문을 멈춘다.

<고찰>

• N-Queen 문제에서도 느꼈지만 대각선이나 마름모에서 쓰이는 스킬은 두고두고 쓰이는 듯 하다. 기억해두자.
• 이렇게 돌려서 테스트 케이스의 경우에는 전부 답이 맞지만 제출하면 47번째에서 막힌다...
• 원인을 찾아보니 위에 4번째 아이디어에서 강조해놓은 구문이 잘못되었다.

 

<해결>

def operation_expense(k):
    return k * k + (k - 1) * (k - 1)
    
for tc in range(int(input())):
    N, M = map(int, input().split())
 
    field = [list(map(int, input().split())) for _ in range(N)]
    homes = []
 
    for y in range(N):
        for x in range(N):
            if field[y][x]:
                homes.append((y, x))
 
    max_profit = len(homes) * M
 
    for k in range(N + 2, 0, -1):
        cur_expense = operation_expense(k)
        if max_profit - cur_expense >= 0:
            num_max_home = 0
            for y in range(N):
                for x in range(N):
                    num_home = 0
                    for h_y, h_x in homes:
                        if abs(y - h_y) + abs(x - h_x) < k:
                            num_home += 1
                    if num_max_home < num_home and num_home * M >= cur_expense:
                        num_max_home = num_home
            if num_max_home:
                break
 
    print('#{} {}'.format(tc + 1, num_max_home))

<기본 아이디어>

• 기본 아이디어는 <시행착오 2>와 거의 같다.
• 서비스를 제공받는 집에서 얻을 수 있는 돈이 비용보다 크거나 같다면 집의 수를 저장하고 반복문을 멈춘다.
• 다시 강조한다. '크거나 같다면' 이다.

<고찰>

• 문제를 자세히 다시 읽어보니 다음과 같이 적혀있었다.

이때, 손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾고,
그 때의 홈방범 서비스를 제공 받는 집들의 수를 출력하는 프로그램을 작성하라.

• 손해를 보지 않으면서란 뜻은 이익이 0이라도 상관없다는 뜻이니 같은 경우도 포함되었어야 했다.
• 문제를 꼼꼼하게 읽지 않아 생긴 단순한 미스다.
• 테스트 케이스가 다 통과되었는데도 이상하게 계속 막힌다면 문제를 처음부터 다시 꼼꼼하게 읽어보자!!