오늘의 회고

브루트포스로 대피소 문제를 풀었다.

---

풀이

틀린 이유

import sys
from itertools import combinations
input = sys.stdin.readline

n, k = map(int, input().split())
x = [0]*n
y = [0]*n
for i in range(n):
    x[i], y[i] = map(int, input().split())


def dist(c):
    b = 0
    for i in range(n):
        a = 100000 
        for j in c:
            temp = abs(x[i] - x[j]) + abs(y[i] - y[j])
            a = min(a, temp)
        b = max(b, a)
    return b
comb = list(combinations(range(n), k))
# answer = INF
answer = 100000
for c in comb:
    answer = min(answer, dist(c))

print(answer)

최댓값의 범위를 x,y의 최댓값인 100000으로 줬더니 67점이 나왔다.
해결: INF로 초기화했다. 이걸 공부하면서 파이썬으로 무한값을 주는 방법을 처음 알았다.

INF = float("INF")

브루트포스 문제라서 combination으로 n개의 집들 중 k개를 뽑아 나올 수 있는 경우의 수를 모두 구하고 이때 나오는 최솟값들 중 가장 큰 값을 찾아 리턴하는 함수를 만들었다.

정답 코드

import sys
from itertools import combinations
input = sys.stdin.readline

n, k = map(int, input().split())
x = [0]*n
y = [0]*n
for i in range(n):
    x[i], y[i] = map(int, input().split())

INF = float("INF")

def dist(c):
    b = 0
    for i in range(n):
        a = INF
        for j in c:
            temp = abs(x[i] - x[j]) + abs(y[i] - y[j])
            a = min(a, temp)
        b = max(b, a)
    return b
comb = list(combinations(range(n), k))
answer = INF
for c in comb:
    answer = min(answer, dist(c))

print(answer)