개구리 점프

아래와 같이 일렬로 배열된 24개의 칸이 있고, 각 칸은 비어 있거나 개구리 한 마리가 들어 있다.

처음에 아래와 같이 15개의 칸에만 개구리가 한 마리씩 놓여 있고 나머지 9개의 칸은 비어 있다.

각각의 개구리는 다음의 규칙에 의해 점프할 수 있다. 점프는 아래의 방식으로만 가능하며, 이외의 다른 이동은 허용되지 않는다.

• (A) 어느 개구리의 바로 오른쪽 칸에 다른 개구리가 있고, 오른쪽으로 두 칸 떨어진 칸이 비어 있으면, 이 개구리는 오른쪽으로 두 칸 떨어진 칸으로 점프할 수 있다.
• (B) 어느 개구리의 바로 왼쪽 칸에 다른 개구리가 있고, 왼쪽으로 두 칸 떨어진 칸이 비어 있으면, 이 개구리는 왼쪽으로 두 칸 떨어진 칸으로 점프할 수 있다.

개구리는 빈 칸으로만 점프할 수 있으며, 칸들 외의 영역으로는 이동할 수 없다.

위의 점프를 임의의 순서로 수행하여 얻을 수 있는 모든 배치를 고려할 때, 개구리들이 놓이게 되는 서로 다른 배치의 가짓수는 모두 몇 가지인가? (단, 개구리는 서로 구별하지 않는다.)

문제 형식

주관식

출처

• KOI 2025 1차대회 고등부 1교시 10번
• KOI 2025 1차대회 중등부 1교시 12번