레이튼 교수와 이상한 마을 99번. 33333 문제 풀기

쉬면서 레이튼 교수와 이상한 마을 방송이 있길래 재밌게 보고 있었다. 크고나서 보니 뭔가 알고리즘에서 보던 익숙한 문제와 개 억지 문제를 구경하던 중 눈에 뛴 문제 1개가 있었다.

1~9 까지의 카드를 모두 사용해서 식을 완성시키는 문제. 어렸을 때는 노가다로 풀었던 기억이 있지만, 지금의 나라면 귀찮아서 컴퓨터로 코드짜서 돌릴 것 같다. 백트래킹 까지 갈 것도 없고 대충대충 짜서 풀어봤다.

using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;

class Baekjoon
{
    public List<int> nums = new List<int>();

    private void MakeNum(int n, int digit, int[] arr, bool[] visited)
    {
        if (digit == 1000000000)
        {
            nums.Add(n);
            return;
        }

        for (var i = 0; i < 9; i++)
        {
            if (visited[i]) continue;

            var calc = arr[i] * digit;
            visited[i] = true;
            MakeNum(n + calc, digit * 10, arr, visited);
            visited[i] = false;
        }
    }

    private void Solution(int n)
    {
        var numArr = new int[9] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        var visited = new bool[9];
        MakeNum(0, 1, numArr, visited);

        foreach (var cardNum in nums)
        {
            var a = cardNum / 10000;
            var b = cardNum % 10000;

            if ((a - b) == n)
            {
                Console.WriteLine($"{a} - {b} = {n}");
            }
        }
    }

    static void Main(string[] args)
    {
        new Baekjoon().Solution(int.Parse(Console.ReadLine()!));
    }
}

그래서 문제 정답

11111
19753 - 8642 = 11111
17953 - 6842 = 11111
19573 - 8462 = 11111
15973 - 4862 = 11111
17593 - 6482 = 11111
15793 - 4682 = 11111
19735 - 8624 = 11111
17935 - 6824 = 11111
19375 - 8264 = 11111
13975 - 2864 = 11111
17395 - 6284 = 11111
13795 - 2684 = 11111
15937 - 4826 = 11111
19357 - 8246 = 11111
13957 - 2846 = 11111
15397 - 4286 = 11111
13597 - 2486 = 11111
17539 - 6428 = 11111
15739 - 4628 = 11111
17359 - 6248 = 11111
13759 - 2648 = 11111
15379 - 4268 = 11111
13579 - 2468 = 11111

22222
31784 - 9562 = 22222
27185 - 4963 = 22222
28715 - 6493 = 22222
31847 - 9625 = 22222
31487 - 9265 = 22222
31748 - 9526 = 22222
27158 - 4936 = 22222
31478 - 9256 = 22222
25718 - 3496 = 22222
28571 - 6349 = 22222
25871 - 3649 = 22222

33333
41286 - 7953 = 33333
41268 - 7935 = 33333

44444
48196 - 3752 = 44444
49816 - 5372 = 44444
54316 - 9872 = 44444
53416 - 8972 = 44444
46297 - 1853 = 44444
49627 - 5183 = 44444
51427 - 6983 = 44444
52138 - 7694 = 44444
51238 - 6794 = 44444
48169 - 3725 = 44444
46279 - 1835 = 44444
46819 - 2375 = 44444
47629 - 3185 = 44444
49681 - 5237 = 44444
46981 - 2537 = 44444
49762 - 5318 = 44444
47962 - 3518 = 44444

55555
59876 - 4321 = 55555
58976 - 3421 = 55555
59786 - 4231 = 55555
57986 - 2431 = 55555
58796 - 3241 = 55555
57896 - 2341 = 55555
59426 - 3871 = 55555
58346 - 2791 = 55555
59867 - 4312 = 55555
58967 - 3412 = 55555
59687 - 4132 = 55555
56987 - 1432 = 55555
61487 - 5932 = 55555
58697 - 3142 = 55555
56897 - 1342 = 55555
61397 - 5842 = 55555
59417 - 3862 = 55555
59768 - 4213 = 55555
57968 - 2413 = 55555
59678 - 4123 = 55555
56978 - 1423 = 55555
61478 - 5923 = 55555
57698 - 2143 = 55555
56798 - 1243 = 55555
61298 - 5743 = 55555
57248 - 1693 = 55555
58769 - 3214 = 55555
57869 - 2314 = 55555
58679 - 3124 = 55555
56879 - 1324 = 55555
57689 - 2134 = 55555
56789 - 1234 = 55555
61289 - 5734 = 55555
58319 - 2764 = 55555
57239 - 1684 = 55555
59831 - 4276 = 55555
57941 - 2386 = 55555
56942 - 1387 = 55555
59723 - 4168 = 55555
58724 - 3169 = 55555
56834 - 1279 = 55555

66666
73158 - 6492 = 66666
71358 - 4692 = 66666
75129 - 8463 = 66666
71529 - 4863 = 66666
73491 - 6825 = 66666
74931 - 8265 = 66666
69513 - 2847 = 66666
69153 - 2487 = 66666
73194 - 6528 = 66666
71934 - 5268 = 66666

77777
84712 - 6935 = 77777
81742 - 3965 = 77777
84172 - 6395 = 77777
81472 - 3695 = 77777
85216 - 7439 = 77777
82516 - 4739 = 77777
85126 - 7349 = 77777
81526 - 3749 = 77777
82156 - 4379 = 77777
81256 - 3479 = 77777

88888
없음

99999
없음

근데 왜 애들 게임에서 정답이 2개 밖에 없는 33333을 문제로...