다음 두 가지 성질을 알 수가 있다.순서가 아무런 상관이 없으니, 편의상 위에서 아래로, 왼쪽에서부터 오른쪽인 순서로 패널을 터치 한다고 하자.
- 한 패널을 두 번 터치하는 것은 터치를 아예 안 한 것과 같다.
- 패널을 터치하는데 순서는 아무 상관이 없다.
일단 원래 문제로부터 약간 변형 시켜보자. 이 변형된 문제에서는 r, c 를 행, 열이라고 했을 때 r>=1 과 c>=1 에 위치한 패널만 터치 할 수 있다고 하자. 그럼 (0,0) 에 위치한 패널의 상태를 바꾸려면 어떤 패널을 터치 해야 할까? 답은 (1,1) 밖에 없다.
일반적으로 현재 (r,c) 패널에 있고 (r-1,c-1) 에 위치한 패널이 꺼져 있다면 (r,c) 패널을 터치를 할 수 밖에 없다는 걸 알 수 있다. 그 반대로 (r-1,c-1)이 켜져 있다면 터치를 하면 안 된다는 것도 알 수 있다.
그럼 다시 원래 문제로 돌아가 보자. 우리는 r>=1 이고 c>=1 일 때 (r-1,c-1) 이 꺼져 있으면 (r,c)를 터치해야 한다는 걸 위 변형된 문제에서 알 수 있었다. 그럼 우리가 고려해야 할 것은 r<1 이나 c<1 일 때 상태이다.
최악의 데이터에서 r<1 이나 c<1 인 패널 개수는15개다. 즉 15개의 패널에 의해 가능한 모든 조합을 다 시도해 본 후, r>=1, c>=1 일 때는 위 변형된 문제처럼 그리디 하게 패널을 터치 하면 된다.
최악의 데이터인 R = 8, C = 8 에 경우에도 최대 215 x 7 x 7 = 1605632 번 정도 돌면 된다. 물론 불가능하다는 것을 알았을 때 루프에서 바로 빠져 나오면 1605632 보다는 훨씬 적게 돌 것이다. 충분히 제한 시간인 1초 안에 들어올 수 있다.