자갈게임 timer 1s memory - MB

지금부터 재미있는 게임을 하나 소개하겠다. 여러분은 조그마한 구멍 12개가 일렬로 뚫려 있는 게임판을 하나 받을 것이다. 각 구멍에 검은색 자갈이 임의로 배치됨으로써 게임은 시작된다. 이 게임의 최종 목표는 검은색 자갈의 개수를 최소로 만드는 것이고, 게임의 룰은 다음과 같다.

연속된 세 개의 구멍 중, 첫 번째와 두 번째 구멍에 자갈이 있고, 세 번째 구멍에 자갈이 없다면 첫 번째 구멍의 자갈을 세 번째 구멍으로 옮길 수 있으며 이 때 두 번째 구멍의 자갈은 빼 낸다.

위와 같이 두 번째와 세 번째 구멍에 자갈이 있 고, 첫 번째 구멍에 자갈이 없다면 세 번째구멍의 자갈을 첫 번째구멍으로 옮길 수 있으며 이 때 두 번째구멍의 자갈은 빼 낸다.

더 이상 빼낼 자갈이 없을 때까지 위의 두 룰을 반복해서 수행한다.

예 –초기상태)

○는 비어있는 구멍, ●는 자갈

위 예는 8번 자갈을 6번 구멍으로 옮기는 방법과 7번 자갈을 9번 구멍으로 옮기는 방법이 있다.

실행방법1 )

실행방법 1로 옮긴 경우를 보자. A상황에서 7번 자갈을 9번 구멍으로 옮긴 후 8번 자갈을 제거한다. 첫 번째 자갈을 제거 후 B 상황이 되어 더 이상 자갈을 빼낼 수 없기 때문에 남은 자갈의 수는 3개로 게임이 끝난다.

실행방법2)

실행방법 2는 8번 자갈을 6번 구멍으로 옮긴다 . 그리고 7번 자갈을 제거하면 B 상황이 되고 , 5번 자갈을 7번으로 옮겨서 하나의 자갈을 더 빼내어 C상황을 만들 수 있게 된다. 최종으로 남는 자갈의 수는 2개로 게임이 끝난다.

이와 같이 자갈을 옮기는 방법과 순서 에 따라 게임의 결과가 다르게 나올 수 있다.