1. 퍼즐을 푸는데 각각의 버튼들은 최대 한 번만 눌러봐도 됩니다 (두 번 누르면 안누른거랑 같으니까 의미없음)
2. 버튼들을 누르는 순서는 상관이 없습니다
2째행/ 3째행/ ...,/ N째행 같이 행단위로 버튼들을 적절히 눌러서 그 윗 행에 있는 모든 전구를 끈다고 합시다
초기상태는 맨 처음 시작상태에서 1째행의 버튼들의 특정 조합을 누른 후의 상태입니다 (총 2^N가지가 되겠죠)
EX)
1) 초기:
0 1 1 0 0
1 0 0 1 1
0 1 0 0 1
0 1 0 0 0
2) 2째행의 버튼들을 눌러서 1째행의 전구를 모두 끄기: 2째행의 2열,3열 버튼을 누르는 조합이 유일
0 0 0 0 0
0 0 0 0 1
0 0 1 0 1
0 1 0 0 0
3) 3째행의 버튼들을 눌러서 2째행의 전구를 모두 끄기: 3째행의 5열 버튼을 누르는 조합이 유일
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 1 0 0 1
4) 4째행의 버튼들을 눌러서 3째행의 전구를 모두 끄기: 4째행의 3,4열 버튼을 누르는 조합이 유일
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
5) 맨 마지막 행의 전구가 모두 0이므로 전구를 모두 끄는게 가능합니다
poirin 6년 전
DFS로 풀었는데 여러가지 안나오는 경우 고려해도 시간복잡도가 2^300은 나오는것 같습니다.
혹시 DP로 푸는건가요?