Microsoft MVP성태의 닷넷 이야기
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일

방탈출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"의 조합으로도 나오기 때문입니다.

첨부된 파일은 위의 코드를 포함한 예제 프로젝트입니다.

(참고로, 이런 글 썼다고 홈지기가 수학을 잘하는 것 같다고 오해는 하지 마시기 바랍니다. ^^)




[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]

[연관 글]






[최초 등록일: ]
[최종 수정일: 6/28/2021]

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 작성자
 



2011-08-24 09시08분
[방실이] 이런식으로 게임 하면...게임 할 맛이 안나요..ㅋㅋㅋ
[손님]
2011-08-26 09시03분
^^ 게임할 맛은 안 나도 프로그램하는 맛은 있죠.
정성태

1  2  3  4  5  6  [7]  8  9  10  11  12  13  14  15  ...
NoWriterDateCnt.TitleFile(s)
12944정성태1/28/2022998.NET Framework: 1143. C# - Entity Framework Core 6 개요
12943정성태1/27/2022715.NET Framework: 1142. .NET 5+로 포팅 시 플랫폼 호환성 경고 메시지(SYSLIB0006, SYSLIB0011, CA1416)파일 다운로드1
12942정성태1/27/2022729.NET Framework: 1141. XmlSerializer와 Dictionary 타입파일 다운로드1
12941정성태1/26/2022547오류 유형: 790. AKS/k8s - pod 상태가 Pending으로 지속되는 경우
12940정성태1/26/2022717오류 유형: 789. AKS에서 hpa에 따른 autoscale 기능이 동작하지 않는다면?
12939정성태1/25/2022839.NET Framework: 1140. C# - ffmpeg(FFmpeg.AutoGen)를 이용해 MP3 오디오 파일 인코딩/디코딩하는 예제파일 다운로드1
12938정성태1/24/2022783개발 환경 구성: 633. Docker Desktop + k8s 환경에서 local 이미지를 사용하는 방법
12937정성태1/24/2022804.NET Framework: 1139. C# - ffmpeg(FFmpeg.AutoGen)를 이용해 오디오(mp2) 인코딩하는 예제(encode_audio.c)파일 다운로드1
12936정성태1/22/2022672.NET Framework: 1138. C# - ffmpeg(FFmpeg.AutoGen)를 이용해 멀티미디어 파일의 메타데이터를 보여주는 예제(metadata.c)파일 다운로드1
12935정성태1/22/2022731.NET Framework: 1137. ffmpeg의 파일 해시 예제(ffhash.c)를 C#으로 포팅파일 다운로드1
12934정성태1/22/2022594오류 유형: 788. Warning C6262 Function uses '65564' bytes of stack: exceeds /analyze:stacksize '16384'. Consider moving some data to heap.
12933정성태1/21/2022692.NET Framework: 1136. C# - ffmpeg(FFmpeg.AutoGen)를 이용해 MP2 오디오 파일 디코딩 예제(decode_audio.c)파일 다운로드1
12932정성태1/20/2022863.NET Framework: 1135. C# - ffmpeg(FFmpeg.AutoGen)로 하드웨어 가속기를 이용한 비디오 디코딩 예제(hw_decode.c) [2]파일 다운로드1
12931정성태1/20/2022772개발 환경 구성: 632. ASP.NET Core 프로젝트를 AKS/k8s에 올리는 과정
12930정성태1/19/2022610개발 환경 구성: 631. AKS/k8s의 Volume에 파일 복사하는 방법
12929정성태1/19/2022698개발 환경 구성: 630. AKS/k8s의 Pod에 Volume 연결하는 방법
12928정성태1/18/2022581개발 환경 구성: 629. AKS/Kubernetes에서 호스팅 중인 pod에 shell(/bin/bash)로 진입하는 방법
12927정성태1/18/2022609개발 환경 구성: 628. AKS 환경에 응용 프로그램 배포 방법
12926정성태1/17/2022674오류 유형: 787. AKS - pod 배포 시 ErrImagePull/ImagePullBackOff 오류
12925정성태1/17/2022685개발 환경 구성: 627. AKS의 준비 단계 - ACR(Azure Container Registry)에 docker 이미지 배포
12924정성태1/15/20221095.NET Framework: 1134. C# - ffmpeg(FFmpeg.AutoGen)를 이용한 비디오 디코딩 예제(decode_video.c) [2]파일 다운로드1
12923정성태1/15/2022625개발 환경 구성: 626. ffmpeg.exe를 사용해 비디오 파일을 MPEG1 포맷으로 변경하는 방법
12922정성태1/14/2022650개발 환경 구성: 625. AKS - Azure Kubernetes Service 생성 및 SLO/SLA 변경 방법
12921정성태1/14/2022547개발 환경 구성: 624. Docker Desktop에서 별도 서버에 설치한 docker registry에 이미지 올리는 방법
12920정성태1/14/2022507오류 유형: 786. Camtasia - An error occurred with the camera: Failed to Add Video Sampler.
12919정성태1/13/2022704Windows: 199. Host Network Service (HNS)에 의해서 점유되는 포트
1  2  3  4  5  6  [7]  8  9  10  11  12  13  14  15  ...