• 백준 15686번

문제

풀이

처음 든 생각

M<=치킨집갯수<=13 이니까 막 풀어도 시간이 괜찮을 것 같다!

시간복잡도

최악의 경우 $_{13}C_{M}$ 인데, 100,000 을 넘지 않는다.

풀이아이디어

파이썬의 조합 combination 라이브러리를 사용한다!
combinations(chicken_arr, m)) # 치킨집 중 m개를 조합으로 뽑느 ㄴ경우

코드

from itertools import combinations

n, m = map(int, input().split())

# 이렇게 바둑판 전체를 한번에 입력받는게 아니라
#city = list(list(map(int, input().split())) for _ in range(n))

# 필요한 정보만 따로 리스트에 저장한다!
chicken, house = [], []

for r in range(n) :
	data = list(map(int, input().split()))
	for c in range(n) :
		if data[c] == 1 :
			house.append(r,c) # 일반 집
		elif data[c] == 2 :
			chicken.append(r,c) # 치킨집

# 모든 치킨집중에서 M개의 치킨집을 뽑는 조합 계산
candidates = list(combinations(chicken ,m))

def get_sum(candidate) :
	result = 0
	# 모든 집에 대하여
	for hx, hy in house :
		# 가장 가까운 치킨집 찾기
		temp = 1e9
		for cx, cy in candidate :
			temp = min(temp, abs(hx-cx)+abs(hy-cy)) # 치킨 거리 계산
		# 가장 가까운 치킨집가지의 거리를 더하기
		result += temp
	# 치킨 거리의 합 반환
	return result

# 치킨 거리의 합의 최소를 찾아 출력
result = 1e9
for candidate in candidates :
	result = min(result, get_sum(candidate))

print(result)

느낀점

• 시뮬레이션 구현
  • '치킨거리'를 구하는 과정이 머리로는 쉽게 이해 되는데
    막상 코드로 어떻게 짤지 바로 떠오르지 않았다.
  • 왜냐면 문제에서는 '이렇게 하면 집~치킨집까지의 치킨거리를 구할수 있다' 인데
  • 막상 문제에서는 '가장 작은 치킨거리의 합' 을구하라고 한다.
  • 이걸 을 구하려면
    • 각 집마다 모든 치킨집까지의 거리를 구한다
    • 그 중 가장 작은 거리 (집~치킨집) 를 찾는다
    • 모든 집마다 이렇게 찾고, 더하면
    • '가장 작은 치킨거리의 합' 을 찾을 수 있다.
  • 나눈.. 첨에 '가장 작은 치킨거리의 합'을 이해를 못했다.
    • '가장 작은 치킨거리의 합' 라는게 집을 기준으로 count 해야하는지 , 치킨집으로 count 해야하는지도 잘 감이 오지 않았다
    • 오히려 치킨집을 기준으로 count 해야한다고 생각했는데, 여러개의 치킨집중에서 m개를 조합으로 뽑기 때문이었다. 조합뽑기=치킨거리 계산을 일원화되어 생각하고 있었는데, 오히려 분리해서생각했어야 했다!
      • (치킨집기준)조합으로 치킨집을 뽑은다음 -> (집기준) 이 경우에서 모든 치킨거리의 최소합 구하기

  • 		for hx, hy in house :
    				# 가장 가까운 치킨집 찾기
    				temp = 1e9
    				for cx, cy in candidate :
    					temp = min(temp, abs(hx-cx)+abs(hy-cy)) # 치킨 거리 계산
    				# 가장 가까운 치킨집가지의 거리를 더하기
    				result += temp
    			# 치킨 거리의 합 반환
    			return result

• 하놔 이렇게 문제 자체를 잘못 이해하면 어떡하냐.... ㄱㅊㄱㅊ 다음부턴 잘할꺼임!