2023/8/11

이코테 p332입니다.

15686번: 치킨 배달

import sys
from itertools import combinations

input = sys.stdin.readline

city = []
N, M = map(int, input().split())  # 50, 13 N^2 -> 2500

for _ in range(N):
  city.append(list(map(int, input().split())))

homes = []
chickens = []

#home chicken 위치를 넣는다.  # O(N^2) N -> 최대 50
for i in range(N):
  for j in range(N):
    if city[i][j] == 1:
      homes.append((i, j))
    elif city[i][j] == 2:
      chickens.append((i, j))
#home chicken 위치를 넣는다.

def getCityChickenDistance(chickens): # O(2N * M)  N-> 최대 50 M-> 최대 13
  cityChickenDistance = 0

  for home in homes:
    i = home[0]
    j = home[1]
    min = int(1e9)

    for chicken in chickens:
      i2 = chicken[0]
      j2 = chicken[1]
      distance = abs(i - i2) + abs(j - j2)
      if min > distance:
        min = distance

    cityChickenDistance += min

  return cityChickenDistance

min = int(1e9)

chickensCandidates = list(combinations(chickens,M))

for candidate in chickensCandidates:  # 거의 최대 13C6 개수의 경우의 수가 있다.
																			# 13*132 정도 니 20 * 200 = 4000 개수
  cityChickenDistatnce = getCityChickenDistance(candidate)
  if cityChickenDistatnce < min:
    min = cityChickenDistatnce

print(min)

# 알고리즘을 작성해보자 !!

# 치킨 거리를 구하는 알고리즘을 작성한다   # 집의 개수 100 치킨 집 개수 13
# -> 1300
# M을 보고 폐업 할 갯수를 판단하고            # 폐업 갯수 13
# 그 갯수대로 제거해보며 치킨 거리를 구해본다    13C6
#                                    13*132
# 제일 치킨 거리가 제일 작은 것을 취한다.

이제 코테 문제 푸는 전략이 잡힌 것 같다.

1. 어떻게 코드를 작성할 것인지 크게 알고리즘을 작성한다. (밑의 주석처럼)
2. 그리고 그렇게 코드를 작성하면 시간 초과가 나지 않을지 빅오를 계산한다
3. 모두 충족되면 그냥 그대로 코딩한다!

푼 방법은 밑에 주석과 같다.

여기서 어떤 치킨매점을 선택할 것인지를 골라야 했는데 combinations를 사용해서 해결하였다.

이코테 정답지를 확인했는데 오 나랑 풀이가 똑같다 👍 좋다좋다

2023/8/13

이코테 p335입니다.

# 오... 푸는 거 포기함..
# 답지는 이해했으니 나중에 잊어버릴때에쯤 도전해보겠습니다