문제 보기 · Level 3 · 2020 KAKAO BLIND RECRUITMENT · 정답률 34% · 푼 사람 5,936명 (2026-09-30 기준)1
문제
둘레 n미터인 원형 외벽에 취약 지점들이 있다. 위치는 정북에서 시계 방향으로 잰 거리 0 ~ n − 1이다. 친구마다 한 시간에 이동할 수 있는 거리가 다르다. 각자 원하는 지점에서 출발해 시계 또는 반시계 방향으로 벽을 따라 움직이며 지나간 지점을 점검한다. 모든 취약 지점을 점검하는 데 필요한 친구 수의 최솟값을 돌려준다. 모두 보내도 안 되면 −1을 돌려준다.
- 1 ≤ n ≤ 200
- 취약 지점 1~15개, 오름차순
- 친구 1~8명, 이동 거리 1~100
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
1단계 · 작은 예로 손으로 풀기
n = 12, 취약 지점 [1, 5, 6, 10], 친구 이동 거리 [1, 2, 3, 4]
- 한 명으로 되나? 가장 멀리 가는 친구(4)가 어디서 출발해도 4미터 안에 지점이 많아야 2개다. 안 된다.
- 두 명이면? 4미터 친구가 5에서 출발해 5, 6을 보고, 3미터 친구가 10에서 출발해 10, 11, 0, 1을 지나며 10과 1을 본다. 된다.
답은 2다. 10에서 1로 넘어갈 때 0을 지나 원을 한 바퀴 도는 부분이 까다롭다.
2단계 · 가장 단순한 방법과 그 속도
친구마다 “안 나감” 또는 “어느 지점에서 어느 방향으로 출발”을 모두 고르면 친구 한 명당 2n + 1가지다. 이 가짓수는 다른 친구의 선택과 상관없이 늘 같아서 곱의 법칙으로 친구 수만큼 곱한다. 8명이면 (2 × 200 + 1)⁸ ≈ 6.7 × 10²⁰가지라 어림없다. 선택지를 줄여야 한다.
3단계 · 핵심 아이디어
선택지를 줄이는 관찰 네 가지다.
- 원 펼치기: 취약 지점 뒤에 “지점 + n”을 한 번 더 붙인다. [1, 5, 6, 10] → [1, 5, 6, 10, 13, 17, 18, 22]. 이제 10에서 1로 넘어가는 것은 10에서 13으로 가는 것과 같다. 13과 1은 12로 나눈 나머지가 같아서(법 12에 대해 합동, 나눗셈과 합동) 원 위의 같은 자리다. 펼친 줄에서 이어진 W개(W는 취약 지점 수)를 덮으면 원 전체를 덮은 것이다.
- 시계 방향만: 반시계로 d만큼 가는 친구는, 끝 지점에서 시계 방향으로 d만큼 간 것과 같은 구간을 본다.
- 취약 지점에서 출발: 아직 안 본 첫 취약 지점에서 출발하는 것이 가장 이득이다. 그보다 앞에서 출발하면 빈 벽을 걷느라 거리를 버린다.
- 멀리 가는 친구부터: k명으로 된다면 가장 멀리 가는 k명으로도 된다. 친구를 더 멀리 가는 친구로 바꾸면 보는 구간이 넓어질 뿐이다.
그래서 k = 1, 2, …로 늘리며, 가장 멀리 가는 k명의 나가는 순서(순열)와 첫 출발 지점만 모두 해 본다. 순서와 첫 지점이 정해지면, 나머지는 “앞 친구가 못 본 첫 지점에서 다음 친구 출발”로 저절로 정해진다.
4단계 · 코드 흐름
- 취약 지점을 펼친 줄
line을 만든다. 이동 거리를 큰 순으로 정렬한다. - k = 1부터 친구 수까지:
- 큰 순 k명의 순서마다, 첫 지점 s = 0 ~ W − 1마다:
- i = s에서 시작한다. 친구를 차례로 보내
line[i] + 거리이하인 지점을 모두 넘긴다. - 친구를 다 쓰기 전에 i가 s + W에 닿으면 k를 돌려준다.
- 끝까지 안 되면 −1.
5단계 · 파이썬 코드
from itertools import permutations
def solution(n, weak, dist):
W = len(weak)
line = weak + [w + n for w in weak] # 원을 한 번 펼친다
dist = sorted(dist, reverse=True)
for k in range(1, len(dist) + 1):
for friends in permutations(dist[:k]): # 가장 멀리 가는 k명의 순서
for s in range(W): # line[s] ~ line[s + W - 1]을 덮는다
end = s + W
i, used = s, 0
while i < end and used < k:
reach = line[i] + friends[used]
used += 1
while i < end and line[i] <= reach:
i += 1
if i == end:
return k
return -1
permutations(a): a의 원소를 늘어놓는 모든 순서를 튜플로 하나씩 준다.permutations([4, 3])은 (4, 3), (3, 4)다.dist[:k]: 큰 순으로 정렬한 리스트의 앞 k개, 즉 가장 멀리 가는 k명이다.- 안쪽
while은 한 친구가 볼 수 있는 지점을 모두 지나간다. 바깥while은 친구를 한 명씩 보낸다.
6단계 · 실행 추적
n = 12, weak = [1, 5, 6, 10], dist = [1, 2, 3, 4]. 펼친 줄은 [1, 5, 6, 10, 13, 17, 18, 22]이다.
| k | 순서 | 첫 지점 | 친구마다 본 지점(펼친 좌표) | 결과 |
|---|---|---|---|---|
| 1 | (4) | 1 | 1, 5 | 실패 |
| 1 | (4) | 5 | 5, 6 | 실패 |
| 1 | (4) | 6 | 6, 10 | 실패 |
| 1 | (4) | 10 | 10, 13 | 실패 |
| 2 | (4, 3) | 1 | 1, 5 / 6 | 실패 |
| 2 | (4, 3) | 5 | 5, 6 / 10, 13 | 성공 |
펼친 좌표 13은 원래 지점 1이다. 답은 2다.
7단계 · 복잡도와 흔한 실수
가장 멀리 가는 k명만 쓰니 고르는 방법은 한 가지로 정해지고, 줄 세우는 \(P(8, k)\)가지 가운데 순서 \(k!\)가지만 남는다. 순서의 수는 k = 1 ~ 8에서 1! + 2! + ⋯ + 8! = 46,233개다. 첫 지점 15개를 곱하면 약 69만 번 시도하고, 시도마다 지점을 많아야 15개 넘긴다. 일부러 느리게 만든 입력(지점 15개, 친구 8명을 다 보내도 실패)에서 0.34초였다.
- 원을 펼치지 않고
(지점 − 출발) % n으로 계산하다가 한 바퀴 넘는 경우를 틀린다. - 친구 순서를 한 가지(큰 순)로만 본다. 순서에 따라 결과가 달라지니 모든 순서를 봐야 한다.
- 반시계 방향까지 따로 해 보느라 시간이 두 배가 된다. 시계 방향만으로 충분하다.