#5559 JOI 깃발

우선 문제에 대해서 고민해주자.

개수를 세기 위해서는 우선 겹치지 않도록 세는 것이 중요하다.

그렇기 때문에 "처음으로 JOI가 나타나는 부분"을 기준으로 dp를 해서 세야겠다는 생각을 했다.

이 dp를 어떻게 해야하는지 고민을 하다보면, 그냥 "JOI가 나타나지 않는 깃발의 수"를 세는게 더 쉬움을 알 수 있다.

 

일단 n, m <= 20이다.

한 번 의심해볼만한 것이 Bitmasking이다.

당연히 비트마스킹에서 1은 "JO"아니면 "JI"의 등장을 의미할 것이다.

대충 생각하면 무려 1 << 20개나 있어보이지만, 1은 서로 이웃할 수 없기 때문에 그 숫자가 몇 개 없다.

따라서 N*M 보드를 돌아다니면서 bitmasking을 관리해주기만 하면 끝