저희팀 우책임님께서 올리신 문제가 있어서 한번 풀어봅니다 ^^;;

오늘 오후에는 김영석 선임이 확률문제를 내주셔서 간만에 재미를 주시더니,
이번에는 우책임님의 알고리즘 문제네요.

문제는 다음과 같습니다.

[1] Bean Problem
(Precondition) 검정콩과 흰 콩들이 섞여서 들어 있는 컵이 하나 있고,
검은콩이 무한대로 들어 있는 자루가 있다.
(Task) 컵에서 두 개의 콩을 꺼내서 두 콩의 색이 같으면 둘 다 버린 후, 검은 콩을 자루에서 하나 꺼내서 컵에 넣는다. 컵에서 꺼낸 두 콩의 색이 다르면 검은콩은 버리고 흰콩은 다시 컵에 넣는다.
(Question 1) 다음과 같은 작업들을 계속 반복한다면 어떻게 될 것인가?
(Question 2) 처음 컵에 흰 콩이 M개, 검은 콩이 N개 담겨 있었다면 마지막 콩의 색깔은 어떻게 결정되는가?

첫 느낌은 재귀적으로 해결하면 되지 않을까 생각했습니다.
재귀가 진행될수록 콩의 갯수는 1개가 줄어들겠고,
재귀의 종결 조건은 콩이 컵에 1개 남을 때가 되겠죠.
그래서 1번의 예상 정답은 '검은콩 or 흰콩이 단 1개만 남는다' 입니다.
(아마 이렇게 답했다간 전 떨어졌겠죠 ^^;;;)

그럼 두번째 문제로 수식으로 다시 생각해보았습니다.
Cup(White, Black)으로 하나의 함수를 정의하고,
White, Black은 각 색에 대한 콩의 갯수로 정의하고,
Cup(M, N) =>Cup(m, n)이 되는 것으로 그 Process 진행으로 표현하였습니다.

1) Cup(1, 1) => Cup(1, 0)으로 White Bean이 남는 것을 알 수 있습니다.

2) Cup(0, M) => Cup(0, 1)도 쉽게 알 수 있습니다.
검은 콩만 있는 컵에 검은콩을 2개빼고, 검은 콩을 넣으니 당연히 검은 콩만 남아있겠죠.

3) Cup(N =2m, 0) => Cup(0, m) => Cup(0, 1)이 됨도 쉽게 유추가 가능합니다.

4) Cup(N = 2m+1, M) => Cup(1, M+m) => Cup(1, 1) => Cup(1, 0)도
위의 수식의 조합으로 알아낼 수 있습니다.

그래서 2번 문제에 대한 제 예상 정답은

검은 콩의 갯수와 무관하게
흰 콩 M의 개수가 홀수개이면 흰 콩이 남고,
짝수개이면 검은 콩이 남는다

입니다.

솔직히 잘밤에 함 심심풀이로 풀어본 것이라 맞는지 모르겠네요

다른 문제들도 흥미를 마구 유발시키는데, 다음번에 천천히 풀어보고,
우책임님께 정답 들으면 다시 기록하도록 하겠습니다.

이올린에 북마크하기