Each of the six faces on a cube has a different digit (0 to 9) written on it; the same is done to a second cube. By placing the two cubes side-by-side in different positions we can form a variety of 2-digit numbers.
For example, the square number 64 could be formed:
In fact, by carefully choosing the digits on both cubes it is possible to display all of the square numbers below one-hundred: 01, 04, 09, 16, 25, 36, 49, 64, and 81.
For example, one way this can be achieved is by placing {0, 5, 6, 7, 8, 9} on one cube and {1, 2, 3, 4, 8, 9} on the other cube.
However, for this problem we shall allow the 6 or 9 to be turned upside-down so that an arrangement like {0, 5, 6, 7, 8, 9} and {1, 2, 3, 4, 6, 7} allows for all nine square numbers to be displayed; otherwise it would be impossible to obtain 09.
In determining a distinct arrangement we are interested in the digits on each cube, not the order.
{1, 2, 3, 4, 5, 6} is equivalent to {3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6} is distinct from {1, 2, 3, 4, 5, 9}
But because we are allowing 6 and 9 to be reversed, the two distinct sets in the last example both represent the extended set {1, 2, 3, 4, 5, 6, 9} for the purpose of forming 2-digit numbers.
How many distinct arrangements of the two cubes allow for all of the square numbers to be displayed?
두 개의 육면체의 각 면에 0~9 사이의 글자가 있는 경우, 두 육면체를 나란히 두면 다양한 2자리 숫자를 만들 수 있다.
예를 들어, 제곱수인 64는 아래와 같이 만들어진다:
실제로, 두 육면체의 숫자를 잘 정하면 100 이하의 모든 제곱수를(01, 04, 09, 16, 25, 36, 49, 64, 81) 표시할 수 있다.
예를 들어, 한 육면체에 {0, 5, 6, 7, 8, 9}, 다른 육면체에 {1, 2, 3, 4, 8, 9}가 있으면 모든 제곱수를 표시하는 한 방법이 된다.
그러나, {0, 5, 6, 7, 8, 9}와 {1, 2, 3, 4, 6, 7}가 9개 제곱수를 모두 표현하기 위해서는 6, 9는 아래위가 뒤집힌 경우를 허용해야 한다. 그렇지 않으면 09를 만들 수 없다. 유일한 배열을 결정하기 위해 각 육면체의 배열은 중요하지만 순서는 아니다.
{1, 2, 3, 4, 5, 6}과 {3, 6, 4, 1, 2, 5}은 동일하다.
{1, 2, 3, 4, 5, 6}과 {1, 2, 3, 4, 5, 9}은 서로 다르다.
그러나, 6과 9가 뒤집어지는 것을 허용했으므로, 마지막 예시 두 가지 모두 2자리 수를 만들기 위한 확장된 집합인 {1, 2, 3, 4, 5, 6, 9}를 나타내고 있다.
제곱수를 표시할 수 있는 서로 다른 육면체 배열은 몇 개 있는가?
--------------------------------------------------------------------------
문제 지문이 긴데, 두 수를 조합해서 제곱수(01, 04, 09, 16, 25, 36, 49, 64, 81)을 만들어낼 수 있는 주사위 번호 조합이 몇가지 만들 수 있는지에 대한 질문이다. 처음에 하나는 10의 자리, 다른 하나는 1의 자리를 두는 조합을 생각했는데, 문제에서 요구하는 것은 주사위가 특정 자리에 고정되지 않고 제곱수를 만들어 낼 수 있는 조합을 요구하기 때문에 조금 더 고민을 해야 되었다.
순서가 다르더라도 동일하다고 했으므로 10개의 숫자(0~9)에서 6개 숫자를 뽑는 조합으로 리스트를 만들고, 두 조합 리스트(주사위 2개)에서 제곱수가 만들어지는 경우를 확인할 수 있도록 했다. 10C6에 해당하는 조합 크기가 210이어서 생각보다 크지 않고, 이 문제를 해결하기 위한 새로운 알고리즘이 있을 것 같지는 않아서 반복문 2개를 이용하는 전수조사(라고 좋게 표현했지만 brute force) 방식으로 해결하기로 했다.
6, 9를 동일한 경우로 판정하는 것은 어렵지 않았는데 오답으로 판정되어 문제의 원인을 찾느라 여러가지 방법을 적용해보느라 해결하는데 시간이 많이 걸다. 실제 문제가 된 것은 두 주사위를 독립사건으로 보고 210x210의 전수 대상으로 조사했지만 이 경우 문제에서 예시로 제시한 {0,5,6,7,8,9}, {1,2,3,4,8,9}와 {1,2,3,4,8,9}, {0,5,6,7,8,9}를 두 번 계산하기 때문에 결과값이 크게 나오고 있었고, 이 부분이 중복되지 않도록 조정하고 나서 정답을 구할 수 있었다.
문제 요구조건을 잘못 이해해서 시간이 많이 걸렸어도 복잡한 알고리즘을 요구하는 문제는 아니었는데, 나중에 확인해보니 처음으로 해결한 40% 난이도의 문제였다.