[platinum4] [해설안봄,알고리즘 분류 안봄] 14939 불끄기

https://www.acmicpc.net/problem/14939

 

 

이 문제는 얼핏 보면 범위가 충분히 비트마스크 dp로 풀 수 있을 것 같지만, 그렇지 않다. 상하좌우까지 같이 불을 키고 끄기 때문에 경계값은 2^10 이 아닌 2^30 이 된다. (아래로 dp를 진행한다고 할때 위, 아래까지 포함하므로)

 

그래서 좀 생각을  해본 결과, dp 계산 없이 단순 O(100)연산으로 불을 모두 끌수 있는지 판단할 수 있다는 것을 발견했다.

 

 

 

 

우하향하는 방향으로 순회하면서  켜진 전구가 있으면 기준점을 기준으로 불을 끄면 된다. 

왜 기준점으로만 불을 꺼야 할까? 

 

위처럼 가운데를 기준으로 불을 끄게 된다면, 우하향 하는 방향으로 불을 꺼야 하는데 위쪽이 다시 불이 켜지게 된다.

즉 우햐향으로 불을 끌 때는 내가 만약 3행 3열을 지금 돌고 있으면 1행 전체, 2행전체, 3행1열, 3행 2열까지는 모두 불이 꺼졌고, 다시 켜지지 않는다는 걸 확정지어야 한다. 그런데 가운데를 기준으로 하거나, 좌,우,하 를 기준으로 할 경우 위쪽이 켜지거나 왼쪽부분이 다시 불이 켜지게 된다. 따라서 '상'을 기준으로 불을 끌 수 밖에 없다.

 

그런데 이것도 예외가 있다.

바로 첫번째 행에서다.

 

 

첫번째 행에서는  다시 켜지는 윗줄이 없기 때문에 (맨 윗줄 이기때문에), '가운데'를 기준으로 잡아도 가능하다.

그렇다면 첫번째 행에서만 가운데를 기준으로 하거나, 상을 기준으로 할 수 있다. (좌, 우 는 어차피 가운데로도 커버가 가능하므로 고려하지 않아도 된다).

따라서 첫줄의 불을 모두 끌 때는 '상' , '가운데'기준으로 모두 할 수 있는 것이다. 

첫줄만 저렇게 모두 끄고 나면, 나머지 줄은 이제 '상'을 기준으로만 불을 끄면 된다.  시간복잡도 O(100)

 

 

처음에 생각한 방법은 백트래킹으로 첫줄을 모두 끄기 위해, 연속 3개가 켜져있을 경우엔 '가운데'기준 or '상' 기준,  1개일 경우에는 '상'기준으로만 끄게 하여 이미 끈 불을 다시는 안키게 설정하였다. 

그러나 이것은 잘못된 생각이였다. 다시 끈 불을 다시 키는 경우가 생기게 되는 경우라도 다시 결국엔 끄기만 하면 되는 것이다. 

맨 윗줄이 오른쪽 그림과 같이 켜져있다고 가정하면, 가운데기준으로 먼저끄고, 상 기준으로 끄는 것이 가능하다.

 

결국 1행에 i열에서 상 기준일지, 가운데 기준일지, 아니면 둘다일지, (이미 꺼져있는 경우라면 상기준, 하기준 둘다 해도 결국 꺼지기 때문에) 모른다. 2~3행은 1행에서 불을 어떻게 껐는지에 따라 모양이 달라진다. 

어떤 모양이여야 전체 불을 끄는지 최소가 되는지는 결국 직접 다 해봐야 하므로, O(90) (2~10행까지 이므로)이다.

1행에서는 i번째일때  상기준 or 가운데 기준 or 둘다 or안건든다(이미 꺼져있으면) 이 4가지 중에 하나이므로 O(4^10)이하일 것이다.

결국 최종 시간복잡도는 4^ 10 * 90 ... 1억회 부근일 것이다. (제한 시간은 1초이므로 간당간당 한 거 같다)