전구와스위치

전구와 스위치 문제는 그리디 문제로 분류되는 유형입니다. N개의 스위치와 N개의 전구가 있을 때 1번째의 스위치를 선택 하는 경우와 선택 하지 않은 경우로 나눠볼 수 있습니다. 이렇게 함으로써 A : 000 B : 010 로 A-B 상태를 보고자 할때 A의 1번째 전구의 상태가 B의 1번째 전구의 상태와 같다면 A의 다음 스위치를 누를 필요가 없게 됩니다. 이렇게 접근해야 하는 이유는 A의 스위치로 변할 수 있는 상태가 각 전구 별로 232 에서 121로 바꿀 수 있기 때문입니다. (232 는 1번째 스위치가 1,2 변할 수 있는 경우의 수 이고 2번째 스위치가 1,2,3 변할 수 있는 경우의 수이고 3번째 스위치가 2,3 변할 수 있는 경우의 수 입니다.) 즉, 이러한 상태를 1번째 스위치를 선택 한 ..