바둑알 이동의 경우의 수

정답) 320

다음과 같이 올수 있는 경우의 수를 더해 보면 320 가지 이다.

이렇게 경우의 수를 모두 세어 주어도 되지만

검은색이 위쪽 흰색 돌에 4번 만나기 위해서는 북동,북,북서 세방향이다.

오른쪽 흰색 돌에 4번만에 만나기 위해서는 북동,동,남동 세방향으로 이동한다.

아래와 왼쪽 역시 동일하다.

결국에는 한방향에 대해서 한번에 3가지씩을 선택할 수 있다.

따라서 한방향으로 이동하는 경우의 수는 3 * 3 * 3 * 3 이다.

이게 4방향이므로 4 * 3 * 3 * 3 * 3 이 된다.

하지만 여기서 각 모서리로 도착하는  4가지 경우가 중복이 발생한다.

왼쪽 상단 모서리로 올라가는 경우 위쪽으로 올라가는 경우와 왼쪽으로 가는 경우의 두가지가 겹친다.

따라서 4귀퉁이값을 빼주면 된다.