이코테 유형별 기출문제

구현

치킨 배달

풀이 특징

• 조합 필요: from itertools import combinations
• 각 집들의 (x, y) 좌표배열과 치킨집들의 (x, y) 좌표배열을 저장
• 치킨집들 중 m개를 조합으로 뽑은 경우에 따라 모든 집들의 최소 치킨거리를 합한 값을 조합별로 최솟값을 저장

# 0: 빈칸, 1: 집, 2: 치킨집
# 치킨 거리: 집과 가장 가까운 치킨집 사이의 거리
# 도시의 치킨 거리: 모든 집의 치킨 거리의 합
# 최대 M개의 치킨집을 골랐을 때 도시의 치킨 거리의 최솟값
from itertools import combinations

def dist(a, b):
    return abs(b[0] - a[0]) + abs(b[1] - a[1])

NONE, HOUSE, CHICK = 0, 1, 2
n, m = map(int, input().split())
house = []
chick = []
for r in range(n):
    row = list(map(int, input().split()))
    for c in range(n):
        if row[c] == HOUSE:
            house.append((r, c))
        elif row[c] == CHICK:
            chick.append((r, c))
# 도시의 치킨 거리 최솟값
minDist = int(1e9)
for case in list(combinations(chick, m)):
    # 선택된 m개의 치킨집기준 도시의 치킨 거리 최솟값
    distSum = 0
    for a in house:
        # 특정 집의 치킨 거리 최솟값
        houseDist = int(1e9)
        for b in case:
            temp = dist(a, b)
            houseDist = min(houseDist,  temp)
        # 특정 집의 치킨 거리 최솟값이 구해지면 도시의 치킨 거리 최솟값에 반영
        distSum += houseDist
    # 선택된 m개의 치킨집기준 도시의 치킨 거리 최솟값이 구해지면 도시의 치킨 거리 최솟값에 반영
    minDist = min(minDist, distSum)

print(minDist)

외벽 점검

from itertools import permutations

def solution(n, weak, dist):
    # 취약 지점 개수
    length = len(weak)
    # 원형을 길이 2배로 늘린 일자형태로 변형
    for i in range(length):
        weak.append(weak[i] + n)
    # 투입할 친구수 초기값은 친구수+1
    answer = len(dist) + 1
    # 취약지점 시작점
    for start in range(length):
        # 친구들 순서나열
        for friends in list(permutations(dist, len(dist))):
            # 투입할 친구수
            count = 1
            # 점검할 수 있는 마지막 위치 = 취약지점 + 가능길이
            position = weak[start] + friends[count - 1]
             # 시작점부터 모든 취약한 지점을 확인
            for index in range(start, start + length):
                # 범위를 벗어난 경우
                if weak[index] > position:
                    # 새로운 친구 투입
                    count += 1
                    # 더 투입이 불가한 경우 종료
                    if count > len(dist):
                        break
                    # 점검할 수 있는 마지막 위치 = 현재 취약지점 + 가능 길이 업데이트
                    position = weak[index] + friends[count - 1]
            # 취약가능한 모든지점을 살펴본 후 최소값 업데이트        
            answer = min(answer, count)
    # 모든 친구 투입에도 불가한 경우
    if answer > len(dist):
        return -1
    
    return answer