[컴퓨팅사고력]공 가져가기 게임

원당이와 길동이가 다음과 같은 게임을 하려고 합니다.

게임의 규칙은 다음과 같습니다.

규칙1) 맨 처음 게임을 시작하는 사람은 모든 공을 한번에 가져가는 것을 제외하고 임의의 수 만큼 공을 가져 갈 수 있습니다.

규칙2) 두번째 가져가는 사람 부터는 한개 이상의 공을 가져가며 상대편이 바로 전에 가져간 공의 2배 이하로만 공을 가져갈 수 있습니다. 즉 첫번째 사람이 1개를 가져갔다면 두번째는 1개 또는 2개 를 가져 갑니다.

규칙3) 마지막 공을 가져가는 사람이 이깁니다.

 

그렇다면 공이 현재 10개가 있습니다.

원당이가 먼저 시작하려고 하는데 원당이가 이길수 있는 방법이 있는지 궁금합니다.

만약 이길수 있다면 원당이는 처음에 몇개를 가져가야 이길 수 있을까요?

여러분이 원당이에게 알려 주세요.

 

정답)

정답) 처음에 2개를 가져가면 이길수 있다.

문제풀이)

2개 인경우 원당이가 1개를 가져가는 경우만 있으므로 항상 진다.

3개인 경우 원당이가 1개 또는 2개를 가져 갈 수 있지만 항상 진다.

4개인 경우 원당이가 1개를 가져가면 길동이는 1개~2개를 가져 갈 수 있는데 여기서 길동이는 상대방에게 2개 혹은 1개를 넘겨 주어야 하기 때문에 원당이가 이길 수 있다.

5개인 경우 원당이가 1개를 가져가면 길동이는 4개를 받으므로 길동이가 이길 수 있다. 2개를 가져가면 길동이는 4개까지 가져 갈 수 있기 때문에 길동이가 이긴다. 따라서 원당이가 이길 수 있는 방법이 없다.

6개인 경우 원당이가 1개를 가져가면 길동이는 5개를 받으므로 길동이가 진다. 따라서 원당이가 이긴다.

7개인 경우 원당이가 1개를 가져가면 길동이가 6개이므로 길동이가 이긴다. 원당이가 2개를 가져가면 길동이 5개 이면서 4개까지 가져갈 수 있지만 모두 가져갈 수는 없다. 따라서 5개를 받은 사람이 이길수 없기 때문에 원당이가 이긴다.

8개인 경우 원당이가 1개를 가져가면 7개를 받은 길동이가 이길 수 있다. 2개를 가져가면 6개를 받은 길동이가 이길 수 있는 경우가 있다. 3개를 가져가면 길동이가 6개까지 가져갈 수 있으므로 원당이가 항상 진다.

9개인 경우 원당이가 1개를 가져가면 8개를 받은 길동이가 항상 지기 때문에 원당이가 항상 이긴다.

10개인 경우 원당이가 1개를 가져가면 9개를 받은 길동이가 이긴다. 2개를 가져가는 경우 8개를 받은 길동이가 4개까지 가져 갈 수 있는데 1개나 2개인 경우는 항상 지는 것은 확인 했고 3개를 가져 가는 경우 그다음이 6개를 가져 갈 수 있으므로 3개 이상은 항상 길동이가 지게 되어 있다.

따라서 원당이가 2개를 가져 간다면 항상 이길 수 있다.

컴퓨팅 사고력

이러한 문제는 컴퓨팅과학에서 동적계획법(Dynamic programming) 방법을 이용하는 것입니다. 2개일때 항상 이기는 사람은 나중에 시작한사람이라는 정보를 기억하고, 3개일때는 그 정보를 이용해서 상대방에게 2개를 넘겨주는 경우를 생각해 보면 됩니다.(여기서는 예외처리가 존재합니다. 2개를 넘겨 주었을때 기존에는 1개만 가져 갈 수 있지만 상대방은 2개까지 가져갈 수 있습니다.) 

이렇게 그 전의 승패 정보를 기록해서 그 정보를 이용해서 문제를 해결해 나가는 방법을 동적계획법이라고 합니다.

동적계획법은 점화식을 기본으로 문제를 가장 작은 단위까지 쪼개서 작은 범위에서 얻어지는 값을 이용하여 큰 범위에 값을 얻어가는 것으로 문제를 해결하는 방법입니다.