Daily Study Logging16 - 카카오 2020 BLIND 외벽점검, 파이썬
May 08, 2020
재도전 했지만 여전히 틀려서 다른 사람의 풀이를 빌려 왔다.
최소한 이 풀이라도 내 것으로 만들었다는 점에서 만족 스럽다.
자세한 풀이는 주석을 참고하자 .
from itertools import permutations
def solution(n, weak, dist):
answer = len(dist) + 1
weak_length = len(weak)
# 1 원형 문제를 해결하기
for i in range(weak_length):
weak.append(weak[i]+n)
#2 가능한 모든 춟발지점 구하기
for i in range(weak_length):
possible_starting_points = [weak[j] for j in range(i, i+weak_length)]
# 3 가능한 친구 순서 모두 구하기
candidates = permutations(dist, len(dist))
# 4 모든 친구가 모든 출발점에서 출발하는 경우 필요한 친구의 수 세기
for friends in candidates:
# 사용한 친구 수
friend_number = 1
# 사용한 친구의 인덱스
friend_idx = 0
# 친구가 커버할 수 있는거리
max_length = possible_starting_points[0] + friends[friend_idx]
for idx in range(weak_length):
# 다음에 가야할 좌표가 커버해야 하는 거리보다 멀리 있으면
if possible_starting_points[idx] > max_length:
# 사람 수 늘리고
friend_number += 1
# 사람수 초과면 중지
if friend_number > len(dist):
break
# 친구도 다음 친구로 이전
friend_idx += 1
# 새로운 친구와 새로운 출발 지점으로 커버 가능 거리 갱신
max_length = possible_starting_points[idx] + friends[friend_idx]
answer = min(answer, friend_number)
if answer > len(dist):
return -1
return answer
print(solution(12, [1, 5, 6, 10], [1, 2, 3, 4]))
'''
문제 해결 방법
1. 원형 문제를 해결 한다. => 길이를 두배로 늘리고 붙여 버리면 된다.
2. 가능한 모든 출발 지점을 구한다.
3. 가능한 모든 사용 인원을 구한다.
4. 가능한 모든 사용인원이 가능한 모든 출발지점에서 출발을 했을때 몇 명이 필요한지 센다.
5. 모든 경우가 지나고 제일 작은걸 정답으로 삼는다.
6. 만약 주어진 사람 수 보다 쓰여진 사람수가 많다면 불가능하단 말이므로 -1