방탈출3 - Room 10의 '중복가능한 조합' 문제를 위한 C# 프로그래밍
요즘, 심심할 때마다 한 번씩 iPad/iPhone의 '방탈출3'라는 게임에 시간을 보내고 있습니다. (짬짬이 하던 것이 오늘 기준으로 Room 10까지 왔군요. ^^)
아이폰 앱리뷰 - 방탈출3무료
; http://www.appstory.co.kr/iphone_apps_review2001
마침 Room 10을 통과했는데요. ^^ "Room 10"에 들어서면 4개의 감옥문을 열어야 하는 곳에서 암산을 유도하는 데 '3번째 문'까지는 그런대로 풀어가다가 4번째 문부터는 슬슬 지리한 숫자 싸움이 되어서... 직업병이 도지기 시작하더군요. ^^;
문제를 대강 설명해 보면 대략 이렇습니다.
예를 들어, 화면에는 270이라는 숫자가 나오고 선택 가능한 숫자들로 다음과 같이 8개의 숫자가 제시됩니다.
26, 52, 37, 17, 75, 89, 23, 94
플레이어는 이 중에서 (중복가능한) 5개의 숫자를 골라서 270이라는 숫자가 합산되어야 합니다.
사실, 게임 내의 '저장하기/불러오기' 기능 및 문제가 어느 정도 반복되어 나타난다는 점을 이용하면 정해진 시간안에 충분히 해당 스테이지를 통과하는 것이 가능한데,,, 제가 ^^ 프로그래머이다 보니 키보드로 손이 가는 것을 어찌할 수 없더군요. ^^ (
프로그래머라면!)
이 문제를 프로그램으로 옮기기 위해선, 적어도 '순열'과 '조합'에 대한 기본적인 이해를 하고 있는 것이 좋습니다. 이에 대해서는 아래의 설명을 참고하시는 것이 좋겠습니다.
순열(順列, permutation)과 조합(組合, combination)
; http://ghebook.blogspot.com/2010/10/permutation-combination.html
자, 그럼 방탈출3에서 나온 감옥문 번호 문제는 순열일까요? 조합일까요?
그렇습니다. ^^ 조합입니다. 게다가, 선택해야 하는 숫자가 5개로 정해져 있기 때문에 경우의 수가 많이 줄어듭니다.
n == 8
r == 5
n! / (n - r)!r! = 8! / 3!5! = 40320 / 720 = 56
56가지 정도면... 만만하지요. 그런데, 불행히도 '방탈출3'에서 제시되는 숫자는 중복으로 고르는 것이 가능합니다. 즉 '중복 가능한 조합'이기 때문에 경우의 수가 늘어납니다.
n == 8
r == 5
nHr = n+r-1 C r
= (8 + 5 - 1)C(5)
= 12 C 5
= 12! / (12 - 5)!5!
= 479001600 / 604800
= 792
오~~~ 문제 하나에 조합 가능한 숫자의 수가 792가지나 되니 머리에 쥐가 날 것 같은데요. 하지만, 실제로 인간이 위의 문제를 풀게 되면 '인식 능력'이 다르기 때문에 792가지나 테스트해 볼 필요까지는 없습니다.
예를 들어, 사람이라면... 26과 52라는 2개의 임의의 숫자로 시작해서, 그 2개를 더하면 78이 되고, 260에서 빼면 182가 됩니다. 이제 남은 8개의 숫자 중에서 '1의 자리' 수만 더해서 10을 넘는가에 상관없이 '2'가 되는 180 근처의 숫자 조합을 찾으면 되는 것입니다.
게다가, 5개의 숫자로 270을 만들어야 하니 평균 50 ~ 60 정도의 균형을 맞추는 숫자들이 선택되어야 하므로 17이라는 값이 3번만 중복되어도 가장 큰 숫자인 94를 남은 2번의 기회에 채워넣어도 270이 절대 넘지 못하기 때문에 이로 인해 잘려나가는 수학적 조합의 수도 존재합니다.
어쨌든... ^^ 프로그램에서는 이런 고려까지 하는 것이 더 귀찮을 수 있기 때문에 말 그대로 처음부터 끝까지 순서대로 '조합'을 해내는 코드를 만드는 것이 편합니다. (사실 웬만한 경우의 수라면, GHz 속도의 컴퓨터에게는 의미가 없지요.)
'조합'을 해주는 코드를 직접 만드는 것도 좋고, 아래의 글에서 소개한 Combination 클래스를 사용하는 것도 좋겠습니다. ^^
Using Combinations to Improve Your Software Test Case Generation
; https://docs.microsoft.com/en-us/archive/msdn-magazine/2004/july/using-combinations-to-improve-your-software-test-case-generation
아쉽게도 '방탈출3'의 문제는 숫자 배열인 반면, 위의 클래스는 문자열 배열을 기준으로 하기 때문에 곧바로 가져다 쓸 수는 없습니다. Combination.cs 파일의 곳곳에 나오는 문자열 배열을 int []로 변경하고, 해당 게임의 문제를 코딩하면 다음과 같습니다.
static void Main(string[] args)
{
int[] elems = new int [] { 26, 52, 37, 17, 75, 89, 23, 94 };
Combination c = new Combination(elems.Length, 5);
while (c != null)
{
int [] result = c.ApplyTo(elems);
if (result.Sum() == 270)
{
Array.ForEach(result, n => Console.Write(n + ","));
Console.WriteLine();
Console.WriteLine("Found");
break;
}
c = c.Successor();
}
}
출력 결과:
26, 52, 75, 23, 94
그런데, 또 한가지 Combination.cs의 문제가 있습니다. 바로 '중복 가능한 조합'을 지원하지 않는다는 것인데요, 이 때문에 146 숫자가 나와야 하는 조합을 찾으면 없다고 나옵니다. (답이, 26,
37, 23, 37, 23이기 때문입니다.)
어쩔 수 없이, Combination.cs 파일의 코드를 '중복가능한 조합'을 산출하도록 변경해 주어야 합니다. 이를 위해서 아래와 같이 4군데의 코드를 손봐야 합니다.
public Combination(long n, long k)
{
if (n < 0 || k < 0) // normally require n >= k
throw new Exception("Negative parameter in constructor");
this.n = n;
this.k = k;
this.data = new long[k];
for (long i = 0; i < k; ++i)
this.data[i] = 0; // 중복 가능하도록 0으로 모두 초기화 (기존 코드에서는 i로 초기화)
}
public Combination Successor()
{
if (this.data.Length == 0) // OR 조건 이하 주석 처리 || this.data[0] == this.n - this.k)
return null;
// 첫 번째 요소와 마지막 요소의 값이 (n - 1)일 때 까지 반복 (기존 코드에는 아래의 조건문이 없음)
if (this.data[0] == this.n - 1
&& this.data[this.k - 1] == this.n - 1)
{
return null;
}
Combination ans = new Combination(this.n, this.k);
long i;
for (i = 0; i < this.k; ++i)
ans.data[i] = this.data[i];
// ans.data[i] == this.n - this.k + i 비교를 다음과 같이 변경
for (i = this.k - 1; i > 0 && ans.data[i] == this.n - 1; --i) ;
++ans.data[i];
for (long j = i; j < this.k - 1; ++j)
{
ans.data[j + 1] = ans.data[i]; // +1 처리하던 것을 제거
}
return ans;
}
"n+r-1 C r"로 계산된 792가지 경우의 수가 맞는지 확인을 위해 다음과 같이 출력해 봅니다.
static void Main(string[] args)
{
int[] elems = new int[] { 26, 52, 37, 17, 75, 89, 23, 94 };
Combination c = new Combination(elems.Length, 5);
int i = 0;
while (c != null)
{
Console.WriteLine(c.ToString());
c = c.Successor();
i++;
}
Console.WriteLine(i);
}
// i == 792 출력
오호~~~ ^^ 정확히 792가 나오는 군요. 이제 다시 게임으로 돌아가서 문제가 제시되는 것마다 풀어주면 해당 스테이지를 간단하게 통과할 수 있습니다. 참고로, 아래는 제가 했을 때 제시된 4개의 문제와 답입니다.
270 ==> 26, 52, 75, 23, 94
146 ==> 26, 37, 23, 37, 23
362 ==> 52, 75, 89, 94, 52
315 ==> 26, 26, 75, 94, 94
물론, 정답이 한가지만 있는 것은 아닙니다. 예를 들어, 315의 경우에 "26, 17, 89, 94, 89"의 조합으로도 나오기 때문입니다.
첨부된 파일은 위의 코드를 포함한 예제 프로젝트입니다.
(참고로, 이런 글 썼다고 홈지기가 수학을 잘하는 것 같다고 오해는 하지 마시기 바랍니다. ^^)
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]