[구현] 외벽 점검

1. 문제

친구들을 활용해 외벽 점검을 하자.

점검이 필요한 외벽의 번호 오름차순으로 주어진다.

각 친구들은 점검할 수 있는 길이가 정해져있다.

 

친구들을 최소한으로 사용해서 외벽 점검을 마쳐라.

2. 입력

# SET - 1
n = 12
weak = [1, 5, 6, 10]
dist = [1, 2, 3, 4]

# SET - 2
n = 12
weak = [1, 3, 4, 9, 10]
dist = [3, 5, 7]

# SET - 3
n = 50
weak = [1]
dist = [6]

# SET - 4
n = 200
weak = [0, 10, 50, 80, 120, 160]
dist = [1, 10, 5, 40, 30]

# SET - 5
n = 30
weak = [0, 3, 11, 21]
dist = [10, 4]

# SET - 6
n = 12
weak = [10, 0]
dist = [1, 2]

3. 출력

# SET - 1
result = 2

# SET - 1
result = 1

# SET - 1
result = 1

# SET - 1
result = 3

# SET - 1
result = 2

# SET - 1
result = 1

4. 풀이

1. 원형의 경우 직선으로 펼쳐라

2. 조건을 보고 완전탐색이 가능한 경우인지 확인하라

3. 완전 탐색이 가능한 경우 (Permutations) 어떤 것을 기준으로 돌릴지 설계하라

 

친구를 순서대로 나열 한뒤

 

직선으로 표현된 곳에 출발점을 기준으로 len(weak)만큼 점검

position 현재 친구가 점검이 가능한 부분을 확인한다.

만약 현재 취약지점이 점검 가능한 거리보다 크면,

필요한 친구 수 + 1

position 현재 취약 지점 + 다음 친구 점검 거리

 

만약 필요한 친구 수가 친구 수를 넘어가면, 점검이 불가능한 경우로 판단하고 break

 

알고리즘 너무 어렵다

5. 코드

# ndb 코드

from itertools import permutations
def solution(n, weak, dist):
    answer = len(dist)+1
    len_weak = len(weak)
    len_dist = len(dist)
    
    # 원형을 직선처럼 변형
    for i in range(len_weak):
        weak.append(weak[i]+n)

	# 취약 start index
    for start in range(len_weak):
    	# 친구 순서 결정
        for friends in permutations(dist, len_dist):
            count = 1 # 친구 1명으로 시작
            # 친구가 점검이 가능한 최대 거리
            position = weak[start] + friends[count-1]
            # 현재 확인하는 취약 지점
            for idx in range(start, start+len_weak):
            	# 점검가능한 최대거리보다 취약지점이 멀면,
                if position < weak[idx]:
                	# 친구 한명 추가
                    count+=1
                    # 만약에 친구수를 넘어가면 불가능한 경우
                    if count > len(dist):
                        break
                    # 아니면, 점검 가능한 거리 최신화
                    position = weak[idx] + friends[count-1]
            
            # 더 적은 친구수로 최신화
            answer = min(answer, count)

	# 점검 가능한 경우가 없을 경우 -1 반환
    if answer > len_dist:
        return -1
                
    return answer

 

O = len(dist)! * len(weak) * len(weak)

8 * 15 * 15

 

# 설계 잘못한 내 코드
def solution(n, weak, dist):
    answer = len(dist)+1
    weak.sort()
    dist.sort()

    if len(weak) == 1 and len(dist) >= 1:
        return 1

    for _ in range(len(weak)+1):
        for i in range(1, len(weak)+1):
            # i 개수에 따라 순서대로 묶는다. (weak까지)
            weak_dist = []
            for j in range(len(weak)//i):
                weak_dist.append(weak[i*j+i-1] - weak[i*j])
            try:
                if len(weak[i*j+i:]) == 1: weak_dist.append(0)
                else: weak_dist.append(weak[-1] - weak[i*j+i])
            except: pass
            temp = dist.copy()
            this_answer = len(weak_dist)
            checking=True
            weak_dist.sort()
            for wd in weak_dist:
                st = len(temp)
                for d in temp:
                    if d >= wd:
                        temp.pop(temp.index(d))
                        break
                # 현재 dist로 해결 못한 경우
                if st == len(temp):
                    checking = False
                    break
            if checking:
                answer = min(answer, this_answer)

        weak.append(weak.pop(0)+n)
        
    if answer > len(dist):
        return -1
                
    return answer

O = len(weak) * len(weak)! * len(dist)

여튼 겁나 김