알고리즘46 :: BOJ_2138_전구와스위치

전구와 스위치 문제는 그리디 문제로 분류되는 유형입니다. 

 

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번째 스위치를 선택 한 경우와 선택하지 않은 경우로 나뉘어서 봐야 합니다. 

 

그리디로 분류 되는 이유는 매 스위치 별로 최적의 순간을 결정하기 때문입니다. 

 

 

Code : 꽥! 클릭 클릭 해주세요.

궁금한게 생기시면 클릭해주세요!!! 서로 배워 가요 😀