아래의 문제는 어떤 문제에서 영감을 받아 직접 변형한 문제입니다.

🚦 출근길을 지켜라! - 교통신호 최적화 문제 🚦

배경 이야기

교통국에서 일하는 ‘교통이’는 출근길 정체를 줄이기 위해 일직선 도로에 있는 신호등 $N$개를 조정해야 한다.

하지만 문제는 이 신호등이 특수한 방식으로 작동한다는 것이다.

  • 교통이는 신호등 번호 $j$를 조작할 수 있다.
  • 하지만 $j$번 신호등을 조작하면, $j$의 배수인 모든 신호등이 동시에 상태를 반전(빨간 ↔ 초록)시킨다.

현재 모든 신호등은 빨간불(0) 상태이다.
교통이는 최소한의 조작만으로 도로의 신호등을 원하는 패턴(초록불=1, 빨간불=0)으로 맞춰야 한다!

입출력 설명

  1. 입력

    • 첫 줄에 테스트 케이스 수 $T$.
    • 각 테스트 케이스에서:
      1. 첫 줄에 신호등 개수 $N(1 \leq N \leq 100)$.
      2. 둘째 줄에 $N$개의 정수(0 또는 1)로 목표 신호 상태가 주어진다.

  2. 출력

    • 각 테스트 케이스마다,
      “#(테스트케이스번호) (최소 조작 횟수)” 형태로 결과 출력.

예제 (교통이의 신호 조정 시뮬레이션)

  • 예제1:
    $N=3$, 목표 상태: [1, 0, 1]

    1. 🛑 처음: [0, 0, 0] (모든 신호등이 빨간불)
    2. 🚦 1번 신호 조작 → [1, 1, 1] (1,2,3번 신호등이 토글됨)
    3. 🚦 2번 신호 조작 → [1, 0, 1] (2번 신호등만 토글됨)
    • ✅ 총 2번 만에 목표 달성!

  • 예제2:
    $N=5$, 목표 상태: [1,1,0,0,1]

    1. 🛑 처음: [0,0,0,0,0] (모든 신호등이 빨간불)
    2. 🚦 1번 신호 조작 → [1,1,1,1,1] (1~5번 신호등이 토글됨)
    3. 🚦 3번 신호 조작 → [1,1,0,1,1] (3번 신호등만 토글됨)
    4. 🚦 4번 신호 조작 → [1,1,0,0,1] (4번 신호등만 토글됨)
    • ✅ 총 3번 만에 해결!

...

아래에는 문제풀이 스포가 있습니다.

...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

이 문제를 푸는 것은 어렵지 않다.
전형적인 그리디 알고리즘이다. 그런데 왜 그리디 알고리즘이 통하냐고 하면 대답하기 쉽지 않다.
대충 이정도로 얼버무릴 수 있을 것 같다.
만약 8번째가 켜져있어서 8번을 클릭해서 켰는데 다시 4번이나 2번을 누르면 말짱도루묵이니까
순차적으로 하지 않으면 엉망이 되고 문제가 어려워진다. 그래서, 그리디이다.
이런 논증은 비약이 엄청 심한 논증이다.
나는 처음 풀 때 이를 다음과 같이 풀었다.

신호등 문제: 그리디와 XOR로 풀어보자

위에서 이미 예시를 보면 감이 오겠지만,
문제의 핵심은 “버튼 $j$를 누르면 $j$의 배수 신호등들이 전부 토글(켜짐 ↔ 꺼짐)된다”는 것입니다.

  • 초기 상태: 모든 신호등이 꺼져 있음(0).
  • 목표: $N$개의 신호등을 각각 원하는 패턴(0 또는 1)대로 켜거나 끄기.
  • 클릭(버튼 누르기) 최소 횟수를 구하기.

예컨대, $N=3$이고 목표가 “1 0 1”이었을 때,
1번 → 2번 신호등을 차례대로 누르면 2번 만에 원하는 결과를 얻을 수 있었죠.

1. 단순 시뮬레이션(그리디) 아이디어

가장 직관적인 풀이는 아래와 같은 그리디 알고리즘입니다.

  1. $j = 1$부터 $N$까지 차례대로 확인한다.
  2. “현재 상태”에서 $j$번째 신호등이 목표 패턴과 다르면 → $j$번 버튼을 누른다.
  3. “현재 상태”에서 $j$번째 신호등이 목표 패턴과 같으면 → 안 누른다.
  4. 이렇게 $N$까지 진행하면 최종적으로 목표 패턴이 완성된다. 
# b[j] = j번 신호등의 목표 상태(0 또는 1) (1-based)
# state[j] = 현재 j번 신호등의 상태
# N = 신호등의 총 개수

state = [0] * (N+1)  # 초기: 모두 꺼짐
click_count = 0

for j in range(1, N+1):
    if state[j] != b[j]:  # 목표와 다르면 클릭
        click_count += 1
        # j의 배수들을 전부 토글
        for k in range(j, N+1, j):
            state[k] = 1 - state[k]

print("최소 클릭 횟수:", click_count)

이 방법이 항상 목표를 만족하는 이유

  • 앞에서부터 순서대로 맞춰놓고, 이미 처리한 앞쪽 신호등을 다시 뒤집지 않는다.
  • 예를 들어, 2번 신호등을 맞추기 위해 1번 버튼을 다시 누르면 1의 배수(모든 신호등)가 또 바뀌면서 엉망이 된다.
  • 따라서 한 번 결정한 건 건드리지 않고, 해당 시점에서 필요한 신호등만 토글하는 방식이 최소 클릭을 보장한다.

2. "그리디가 왜 최적(최소 클릭)인지?" - 직관적인 설명

  • 이미 한 버튼을 두 번 클릭하는 것은 의미가 없다(두 번이면 원상 복구).
  • 한 번 결정한 걸 또 뒤집으면 앞에서 맞춰둔 다른 신호등들까지 바뀌면서 서로 충돌 가능성이 높아지고, 클릭 횟수도 증가할 뿐이다.
  • 필요할 때 한 번만 누르는 것이 결국 최소로 누르는 방법이다.

이 정도로도 어느 정도 이해할 수 있지만,
조금 더 엄밀하게 증명하려면 XOR(모듈로 2) 관점에서 보는 것이 더 깔끔하다.

3. XOR(모듈로 2)로 풀이하기

3.1 문제를 “모듈로 2 선형방정식”으로 만들기

  1. “$j$번 버튼을 누르는지 말지는 0/1로 표현”

    • $x[j] = 1$이면 $j$번 버튼을 ‘홀수 번’ 누른 것,
    • $x[j] = 0$이면 ‘아예 안 누르거나 짝수 번’ 누른 것(결국 효과 없음).

  2. $j$번째 신호등의 최종 상태 = “$j$의 배수 버튼”들을 XOR한 값

    • 예: 6번 신호등은 (1번 버튼, 2번 버튼, 3번 버튼, 6번 버튼)이 각각 1로 눌렸다면 그 개수만큼 토글됨.
    • 결국 짝수 번이면 0, 홀수 번이면 1. → XOR 연산과 동일.

  3. 목표 패턴 $b[j]$에 맞추려면,
    $$ b[j] = \bigoplus_{d \mid j} x[d]. $$

    • $d\mid j$는 $j$의 약수를 의미.
    • 혹은 $j$의 배수인지 약수인지 관점이 다를 뿐, 같은 원리이다.

3.2 전진 대입(Forward Substitution)으로 해 구하기

$$
x[j]
=
b[j] \oplus
\Bigl(\oplus_{\substack{d < j \ d \mid j}} x[d]\Bigr).
$$

  • 즉, $j=1$부터 $N$까지 순서대로, 이미 결정된 $x[1], x[2], \dots, x[j-1]$와 목표 $b[j]$를 보고 $x[j]$를 0 또는 1로 결정할 수 있다는 뜻이다.
  • 이것이 실제 코딩에서는 “현재 상태와 목표가 다르면 클릭”으로 구현되는 것이다. 
T = int(input().strip())
for test_case in range(1, T+1):
    N = int(input().strip())
    b = list(map(int, input().split()))
    # b[i]는 i번째 신호등의 목표 상태 (0 or 1), 여기서 i는 0-based

    # state: 현재 신호등 상태(모두 0부터 시작), 0-based 맞춰서 사용
    state = [0]*N  
    click_count = 0

    # 그리디 시뮬레이션
    for i in range(N):
        if state[i] != b[i]:
            click_count += 1
            # i의 배수(0-based에서는 i, i+(i+1), ...)를 토글
            # 단, 인덱스는 0-based, 버튼번호는 (i+1)
            step = i+1
            for k in range(i, N, step):
                state[k] = 1 - state[k]

    print(f"#{test_case} {click_count}")

4. 마무리

  • 단순히 시뮬레이션하면 그리디처럼 보이지만, 본질적으로 XOR(모듈로 2) 성질이 핵심이다.
  • 전진 대입(Forward Substitution) 방식으로 푸는 것이 최적임을 증명할 수 있다.
  • 실제 코드로 구현할 때는 단순히 “목표와 다르면 클릭”을 수행하면 된다.

이제 신호등 토글 문제를 가장 효율적으로 푸는 방법을 확실히 이해했을 것이다.

5. 추가 예시와 함께 살펴보기

이번에는 실제로 XOR 관점에서 버튼을 어떻게 결정하는지, 구체적인 예시를 통해 확인해 보겠습니다.

예제 1: $N=3$, 목표 상태: $[1, 0, 1]$

1) 초기 상태 및 방정식

  • 초기 신호등 상태: $[0, 0, 0]$
  • 목표 상태: $[1, 0, 1]$

신호등 $j$에 대응하는 버튼을 $x[j]$라고 하면,

  • $ b[1] = x[1] $
  • $ b[2] = x[1] \oplus x[2] $
  • $ b[3] = x[1] \oplus x[3] $

목표 $ b = [1, 0, 1] $을 만족하려면,

2) 전진 대입 순서

  1. $j=1$:

    • $ x[1] = b[1] = 1 $
    • (버튼 1번을 누른다 → 모든 신호등이 한 번씩 토글되어 $[1,1,1]$이 됨)

  2. $j=2$:

    • $ b[2] = 0 $, 이미 $x[1] = 1$이라고 할 때,
    • $ x[2] = b[2] \oplus x[1] = 0 \oplus 1 = 1 $
    • (버튼 2번을 누르면 2의 배수인 신호등 2번, 4번(없음)은 토글 → 실제로는 $[1,(1→0),1]$이 되어 $[1,0,1]$)

  3. $j=3$:

    • $ b[3] = 1 $, 이미 $x[1] = 1$.
    • $ x[3] = b[3] \oplus x[1] = 1 \oplus 1 = 0 $
    • (즉, 버튼 3번은 안 누른다)

결국 $\mathbf{x} = (1,1,0)$ 로,
버튼 1번, 2번만 누르면 2번의 클릭으로 끝납니다.

예제 2: $N=5$, 목표 상태: $[1, 1, 0, 0, 1]$

  1. 초기 상태: $[0, 0, 0, 0, 0]$
  2. 목표 상태: $[1, 1, 0, 0, 1]$

버튼을 $x[1] \dots x[5]$라 할 때, 신호등별로:

  • $ b[1] = x[1] $
  • $ b[2] = x[1] \oplus x[2] $
  • $ b[3] = x[1] \oplus x[3] $
  • $ b[4] = x[1] \oplus x[2] \oplus x[4] $
  • $ b[5] = x[1] \oplus x[5] $

목표 $[1,1,0,0,1]$을 만족하려면,

  • $ j=1:, x[1] = 1 $
  • $ j=2:, x[2] = b[2] \oplus x[1] = 1 \oplus 1 = 0 $
  • $ j=3:, x[3] = b[3] \oplus x[1] = 0 \oplus 1 = 1 $
  • $ j=4:, x[4] = b[4] \oplus x[1] \oplus x[2] = 0 \oplus 1 \oplus 0 = 1 $
  • $ j=5:, x[5] = b[5] \oplus x[1] = 1 \oplus 1 = 0 $

즉, $\mathbf{x} = (1,0,1,1,0)$.
이를 시뮬레이션하면 실제로 3번(3,4,1 - 순서는 다를 수 있음) 정도 누르면 $[1,1,0,0,1]$을 만들 수 있습니다.

(주의): 예시 해석에서는 약수/배수 구분 등으로 인해 실제 “누르는 순서”가 달라 보일 수 있지만,
결론적으로 XOR 전진 대입이 “필요한 버튼만 1번씩” 골라내어 최소 횟수로 신호등을 맞춘다는 사실은 동일합니다.

6. 교환(Exchange) 증명 간단 스케치

혹시 “더 적게 누르는 해”가 있을 수 있다고 생각한다면, 아래 교환 논리를 대입해 볼 수 있습니다.

  1. 가정: 어떤 해 $\mathbf{x}^{\text{opt}}$가 $\mathbf{x}^{\text{greedy}}$보다 적은 클릭으로 목표를 만족시킨다고 치자.
  2. 중복 클릭 제거: 버튼을 짝수 번 누르면 ‘안 누른 것’과 동일하므로, $\mathbf{x}^{\text{opt}}$ 역시 최대 1번씩 누른 형태로 정규화할 수 있음.
  3. 앞에서 뒤로 교환: 1번 버튼부터 비교해가며, $\mathbf{x}^{\text{greedy}}$와 다르게 눌렀다면 그 차이를 교환(토글)하는 과정에서,
    뒤 신호등 상태가 뒤섞이지만, 결과적으로 클릭 수를 더 줄일 수 없음을 보일 수 있다.
  4. 결론: $\mathbf{x}^{\text{greedy}}$로 바꾸더라도 클릭 수가 증가하지 않는다면, 그리디 해 역시 최적해와 동일한 비용을 가진다.

7. 더 큰 N에서의 시간 복잡도?

  • 그리디 시뮬레이션 방식은 최대 $O(N^2)$ 정도로 동작하며, $N \le 100$ 이면 충분히 빠릅니다.
  • XOR 전진 대입 방식도 비슷한 복잡도를 가집니다.
  • 어떤 방법이든, N=100 수준에선 거의 순간에 해결이 가능하므로 최적화 고민은 크게 필요 없습니다.

8. 결론 & 한 줄 요약

  1. 버튼 토글 문제는 “한 버튼을 여러 번 누르느냐(짝수·홀수)”가 중요하므로, XOR(=모듈로 2) 문제로 볼 수 있다.
  2. 그리디 시붬레이션(앞에서부터 필요 시 클릭)이나 전진 대입(XOR 방정식 풀이) 모두 최소 클릭을 보장한다.
  3. “한 번 결정한 걸 다시 뒤집는 건 낭비”라는 점이 이 문제를 단순화시킨다.

9. 마무리

이상으로 신호등 토글 문제를 그리디 & XOR 관점에서 푸는 전반적인 과정을 살펴봤습니다.

  • 시뮬레이션 코드도 간단하고,
  • 수학적 증명(모듈로2, XOR)도 깔끔하기 때문에,
  • 자신 있게 “최소 클릭”임을 주장할 수 있습니다.

+ Recent posts

티스토리툴바