동적 계획법(Dynamic Programming) 경우의 수 문제 1 - 비대칭 타일링

문제 파악

원래 타일 개수에서 대칭되는 타일의 개수만 빼면 되는 것이므로, 대칭 타일의 수를 계산하는 DP알고리즘에 비대칭 타일의 개수만 계산해서 빼주면된다.
비대칭 타일의 개수는 짝수일 경우 홀수일 경우를 나눠서 생각하면 원래 칸의 숫자 N을 2로 나눠서 간단히 계산할 수 있다.

이 문제는 경우의 수가 매우 커서 모듈로 연산자가 반드시 필요한데, 모듈로 연산자에 대한 생각이 짧아서 결국 답을 띄우지는 못했다.

올바른 풀이 (모듈로 연산자)

모듈로 연산자를 제대로 고려하지 않아 답이 음수가 되는 경우가 발생했는데, 결국 모듈로 연산자를 통해 나온 답은 연산자보다 무조건 작은 수가 나오며, 음수가 나온 경우 모듈로 연산자를 다시 한번 더 해주면 원래의 답을 구할 수 있다.