문제 접근
2차원 확장 문제는 항상 아이디어 생각해내기 어려운 축에 속하는 것 같다. 저번 비숍 문제도 그렇고 항상 아이디어를 스스로 생각해내기 힘들고, 인터넷의 도움을 빌려도 아이디어가 참신해서 감탄만 나왔지 이걸 내가 생각해낼 수 있었을까에 대해서는 의문부호만 남는다. 스스로 아이디어를 생각해내고 풀 수 있는 능력이 진짜 프로그래밍 실력이 아닌가 다시 한 번 느끼게 해주는 문제였다.
아무튼 문제로 다시 돌아가보자면, 전구는 100개 고정이고 같은 스위치를 2번 이상 누를 필요가 없다. 결과가 같기 때문에 횟수만 늘어나기 때문이다. 그렇다 쳐도 모든 경우의 수를 고려하자니 2^100으로 무조건 TLE가 나게 된다. 무슨 방법이 없을까.
Greedy
일단 이 문제는 그리디+브루트포스이다. 왜 그리디냐면 첫 줄에서 어떤 스위치를 누를 지 결정한다면 나머지 줄도 전부 결정되기 때문이다. 첫 줄을 결정하면 첫 줄을 더 바꿀 수 있는 스위치는 두 번째 줄밖에 존재하지 않으므로 두 번째 줄이 결정될 수밖에 없고, 나머지 줄도 차례로 결정된다. 이는 그리디 방식이고, 첫 번째 줄은 2^10가지, 총 1024번 브루트포스를 적용하면 모든 경우에 대해 고려하게 된다. 모두 끌 수 있는 경우 중 가장 최소한의 스위치를 누른 것의 횟수만 출력하면 되므로 이에 대한 변수만 추가로 구현해주면 해결된다.
Bitmasking
기여 댓글 중에 잘 구현만 하면 비트마스킹까지 필요하진 않다고 했지만, 구현할 경우 훨씬 빠르게 계산이 가능하다(크게 구현이 어렵지도 않다). 나의 경우 각 줄마다 하나의 정수로 나타낸 뒤 계산하였지만, 전체 100개의 전구를 하나의 정수로 구현하여 더 빨리 푸는 방법도 존재한다(물론 가독성은 심각하게 떨어진다). 어떻게 하든 비트마스킹으로 변환하면 기호를 그대로 사용하는 것보다 훨씬 빠르게 계산할 수 있다. 2가지 상태를 자주 토글하는 문제를 보면 비트마스킹을 떠올리는 습관을 길들여야 겠다.
결론
아이디어가 참신하고 재밌는 문제이다.
문제
