We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.
The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.
1부터 n까지 숫자가 각 자리에 한 번씩 사용되었으면 그 n자리 숫자를 pandigital이라 부른다. 예를 들어, 5자리 숫자 15234는 1에서 5 pandigital이다.
7254는 39x186=7254로 승수, 피승수, 곱이 1에서 9 pandigital이므로 특이하다.
승수/피승수/곱이 1에서 9 pandigital인 숫자의 곱의 합을 구하시오.
힌트: 어떤 곱은 한 가지 이상의 방법으로 구할 수 있는데 합계에서 한 번만 포함되어야 한다.
--------------------------------------------------------------------------
pandigital이라는 단어는 처음 보는데 검색해봐도 한글로 대응되는 단어가 나오지 않았다.
간단히 생각하면 1~98765432까지 승수와 피승수를 이중으로 반복하면서 곱을 구해서 승수, 피승수, 곱이 1에서 9 pandigital인지 판정하고, 곱의 중복을 제거하여 더하면 된다. 하지만, 불필요한 계산이 많이 포함되어 시간이 엄청 오래 걸리므로 좀 더 빠른 속도로 구할 수 있는 개선방안이 필요하였다.
'승수x피승수=곱' 관계에서 예시는 2자리x3자리=4자리인 경우이다. (3자리x2자리=4자리와 같이 동일한 결과가 나올 경우를 제외하고) 이 외에 가능한 경우를 생각해 보면, 1자리x4자리=4자리 밖에 없다.
승수가 1자리이고 피승수가 4자리인 반복문과 승수가 2자리이고 피승수가 3자리인 반복문에서 pandigital 숫자 여부를 판정하고, 결과를 집합으로 변형하여 중복을 제거하고 합계를 구하였다.
pandigital 숫자 여부를 판정하는 것은 승수/피승수/곱의 자리수를 확인하고 합집합을 만들어서 1~9가 있는 집합과 동일한지 비교하거나, 1~9가 있는 집합에서 승수, 피승수, 곱의 차집합을 차례로 구해서 null이 되는지 확인하는 등 개인 성향에 따라 여러가지 방법이 가능할 것이다.