0부터 9까지의 수를 사용해 규칙에 맞는 수를 만들기

0부터 9까지 10개의 숫자를 모두 사용해서 규칙에 맞는 수를 만드는 문제이다. 규칙은 단순하다.

원문: http://blog.naver.com/PostView.nhn?blogId=kyaryunha&logNo=220923287298

• 첫번째 숫자까지 1로 나눠진다.
• 두번째 숫자까지 2로 나눠진다.
• ...
• n번째 숫자까지 n으로 나눠진다.

그리고 이 숫자는 0-9 팬디지털 숫자이므로 같은 숫자를 두 번 쓸 일은 없다.

원문에서는 C로 코드를 작성한 거 같던데 5분 내외에 답을 구하고 있다. 여기서는 파이썬으로 풀이해본다.

팬디지털 숫자이므로 1,023,456,789~9,876,543,210까지의 범위를 루프로 돌기보다는 각자리에 사용될 숫자를 추출해서 돌아본다. 여기서 사용된 숫자를 피해서 추출하는 로직을 더해주면 반복해야 하는 범위가 크게 줄어들 수 있다.

재귀함수를 통해서 계산해보자.

1. 이 함수의 인자는 세 개로

   1. 지금까지 단계에서 만들어진 숫자값
   2. 여기에 사용된 숫자 집합
   3. 단계 깊이값.

2. 단계 깊이는 1~10 이며 10보다 커진 경우 0개의 숫자를 모두 썼기 때문에 값을 리스트로 감싸서 리턴한다.

3. 앞의 숫자가 고정된 상태에서 뒤의 숫자를 검사했을 때, 답이 2개 이상인 경우가 있기 때문에 결과는 항상 [int] 타입이어야 한다.

이 함수를 0과 빈 집합을 주고 실행하면 최종적으로는 조건을 만족하는 모든 10자리 정수값을 얻어낼 것이다.

check(n, level, s) -> [int]:
  if level > 10: return [n]
  result = []
  for x in (x for x in range(10) if x not in s):
    m = n * 10 + x
    if m % level is not 0: 
      continue
    s.add(x)
    temp = check(m, level+1, s)
    ## 비어있지 않은 결과를 받았다면 결과 취합
    if temp:
      result += temp
  return result

%time print(check(0, 0, set())
## [3816547290]
## Wall time: 4 ms

답을 만족하는 값은 단 하나만 존재하며, 전체 처리 시간은 3ms.