문제 보기 · Level 1 · 2025 카카오 하반기 1차 · 정답률 30% · 푼 사람 5,117명 (2026-09-30 기준)1
문제
신호등 n개가 초록 → 노랑 → 빨강을 반복한다. 색마다 지속 시간은 신호등마다 다르고, 모두 1초에 초록으로 시작한다. 모든 신호등이 동시에 노란불인 가장 이른 시각(초)을 돌려준다. 그런 시각이 없으면 −1을 돌려준다.
- 2 ≤ n ≤ 5
- 색별 지속 시간 1~18, 한 주기(초록+노랑+빨강) 3~20초
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
- 완전탐색: 1초부터 차례로 모두 확인한다. 어디까지 확인하면 되는지가 핵심이다.
- 최대공약수와 유클리드 호제법: 여러 주기가 함께 처음으로 돌아오는 시간은 최소공배수다.
- 나눗셈과 합동: 6단계의 ≡(합동) 기호가 여기서 나온다. 최소공배수 \(L\)은 모든 주기 \(c\)로 나누어떨어지므로 \(t + L \equiv t \pmod c\)이고, 그래서 \(L\)초마다 모든 신호등의 색이 되풀이된다.
1단계 · 작은 예로 손으로 풀기
신호등 A = [초록 1, 노랑 1, 빨강 1] (주기 3), B = [초록 2, 노랑 1, 빨강 1] (주기 4)
| 초 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| A | 초 | 노 | 빨 | 초 | 노 | 빨 | 초 | 노 | 빨 | 초 | 노 | 빨 |
| B | 초 | 초 | 노 | 빨 | 초 | 초 | 노 | 빨 | 초 | 초 | 노 | 빨 |
11초에 처음으로 둘 다 노랑이다. 12초가 지나면 A와 B 모두 처음 모습(1초)으로 돌아간다. 12는 3과 4의 최소공배수다.
2단계 · 가장 단순한 방법과 그 속도
1초부터 하나씩 늘리며 모든 신호등이 노랑인지 본다. 문제는 언제 멈추나다. 답이 없는 경우(−1)가 있어서, 멈출 곳을 정하지 않으면 영원히 돈다.
멈출 곳은 모든 주기의 최소공배수다. 주기가 3~20인 수 다섯 개의 최소공배수는 가장 커도 1,007,760(16, 15, 13, 17, 19)이다. 약 100만 초를 확인하는데, 한 시각에서 첫 신호등이 노랑이 아니면 나머지는 보지 않으므로 실제로는 0.2초 안쪽이다(이 컴퓨터에서 잰 값).
3단계 · 핵심 아이디어
- 한 신호등의 색: 주기 c = 초록 + 노랑 + 빨강이다. 시각 t(1부터)에서 주기 안의 위치는
(t - 1) % c다. 0부터 세어초록 ≤ 위치 < 초록 + 노랑이면 노랑이다. - 어디까지: 모든 신호등을 합친 모습은 주기들의 최소공배수 L마다 똑같이 되풀이된다. 1초부터 L초까지 없으면 영원히 없다. 이유는 완전탐색 문서의 “반복되는 것은 한 바퀴만 본다”에 있다.
4단계 · 코드 흐름
- 주기들의 최소공배수 L을 구한다.
- t = 1부터 L까지, 모든 신호등이 노랑이면 t를 돌려준다.
- 끝까지 없으면 −1을 돌려준다.
5단계 · 파이썬 코드
from math import lcm
def solution(signals):
period = 1
for g, y, r in signals:
period = lcm(period, g + y + r) # 모든 주기의 최소공배수
for t in range(1, period + 1):
if all(g <= (t - 1) % (g + y + r) < g + y for g, y, r in signals):
return t
return -1
math.lcm(a, b): 최소공배수다(파이썬 3.9부터). 여러 개는 하나씩 겹쳐 구한다.all(조건 for … in …): 모든 신호등에서 조건이 참이면 참이다. 하나라도 거짓이면 그 자리에서 멈추고 거짓을 돌려준다.g <= 위치 < g + y: 위치가 초록 구간(0 ~ g−1) 다음, 노랑 구간(g ~ g+y−1)에 있는지 본다.
6단계 · 실행 추적
signals = [[2, 1, 2], [5, 1, 1]] (주기 5와 7, 최소공배수 35)
- 신호등 1은 위치 2일 때 노랑 → t − 1 ≡ 2 (mod 5) → t = 3, 8, 13, 18, …
- 신호등 2는 위치 5일 때 노랑 → t − 1 ≡ 5 (mod 7) → t = 6, 13, 20, …
처음 겹치는 t는 13이다. 코드도 t = 1, 2, …를 확인하다 13에서 돌려준다.
5와 7은 공약수가 1뿐이라 중국인의 나머지 정리에 따라 두 조건이 t − 1 ≡ 12 (mod 35) 하나로 합쳐진다. 노랑은 늘 1초 이상이라 신호등마다 노랑인 위치가 있다. 그래서 같은 까닭으로 주기들이 쌍마다 서로소이면 답이 늘 있고, −1은 어떤 두 주기에 1보다 큰 공약수가 있을 때만 나온다.
7단계 · 복잡도와 흔한 실수
최소공배수 L까지 n개씩 보니 \(O(L \cdot n)\)이다. L은 가장 커도 약 100만이다.
- 시각을 0부터 세서 한 칸씩 어긋난다. 이 문제는 1초에 초록으로 시작한다.
- 멈출 곳 없이
while True로 돌려 답이 −1인 입력에서 끝나지 않는다. - 멈출 곳을 주기들의 곱으로 잡아도 맞지만, 더 오래 걸린다.