외벽 점검

programmers.co.kr/learn/courses/30/lessons/60062

코딩테스트 연습 - 외벽 점검

from itertools import permutations

def solution(n, weak, dist):
    cur = [] # 현재 투입되는 친구들

    while dist: # 모든 친구들이 투입될때 까지
        cur.append(dist.pop()) # 탐색 거리가 긴 친구부터 한 명씩 추가
        distCases = permutations(cur, len(cur)) # 탐색 순서 순열
        weakCases = [weak[:] if i == 0 else weak[i:] + [w + n for w in weak[:i]] for i in range(len(weak))] # 점검 순서 경우들
        for distCase in distCases:
            for weakCase in weakCases:
                idx = 0 # 처음 점검 포인트의 인덱스
                for friend in distCase: # 한 명씩 출발
                    start = weakCase[idx] # 해당 친구의 출발 지점
                    for i in range(idx, len(weakCase)):
                        if weakCase[i] > start + friend: # 현재 친구 탐색 범위 밖이면 다음 친구 차례로
                            idx = i; break # 다음 친구의 출발 포인트 인덱스 초기화
                        if i == len(weakCase) - 1: return len(cur) # 모든 외벽을 점검했으므로 현재 투입인원 반환

    return -1 # 외벽 점검의 모든 케이스를 통과 못함

→ 완전 탐색에 그리디 개념을 추가해서 1명 부터 탐색 인원을 늘리며 모든 점검 케이스를 조사하는식으로 구현하니까 통과.

 

애초에 완전 탐색으로 푸는것을 의도한 문제 같아서 처음 dfs로 접근 했었는데 테스트케이스 2개가 절대로 통과 안됨.

절~대