백준 1048번: 유니콘

잠이 잘 안와서 가볍게 쓰는 글.

유니콘의 이동 경로대로 문자열을 만들 때 가능한 경우의 수를 구하는 문제.

 

유니콘은 나이트랑 비슷하게 움직이는데, 나이트는 (2칸, 1칸)을 움직이는 대신 유니콘은 (3칸 이상, 2칸 이상)을 움직여야 한다.

 

유니콘이 이동할 수 있는 곳들을 보드판에 나타내보면 다음과 같다. 상당히 예쁜 모양.

 

같은 맥락에서, 색칠된 위치에 유니콘이 있었다면 다음 턴에 Uni의 위치로 이동가능하다는 말도 된다.

결국 맨 처음에 문자열의 0번 위치와 같은 문자들이 놓인 보드판에 경우의 수 1씩을 할당하고,

그 다음부터는 문자열과 같은 문자가 쓰여진 보드판에 저 위치의 경우의 수의 합을 차례로 할당하면 된다.

 

보드판 크기가 300이고 L은 26이므로 복잡도는 단순 구현시 $300^4 \times 50$ 정도가 나오는데, 문제가 많은 복잡도이다.

이를 어떻게 줄일 것인가가 관건인데, 2차원 부분합 배열을 이용하면 된다.

 

나는 모양이 해괴해서 그런지 부분합 배열 생각을 못했었는데, 색칠된 부분의 합을 구하려면 6개의 부분합을 구하면 된다.

(전체) - (가로 3줄 전체) - (세로 3줄 전체) - (5*5짜리 정사각형) + (3*5짜리 가로 직사각형) + (5*3짜리 세로 직사각형)

을 진행하면 해당 색칠된 부분이 나온다.

 

잘 알려져있듯 2차원 부분합은 4번의 연산을 통해 얻어낼 수 있으므로 한 칸에 24번의 연산으로 값을 얻어낼 수 있다.

이 경우 복잡도가 $300^2 \times 24 \times 50$ 로 감소한다.

 

1048.cpp