Repeatless Numbers

문제: REPEATLESS / 경우의 수

[해결책 / 후기]

제한 시간이 10000ms(10초)라고 해서 만만하게 볼 문제가 아니었다.

처음에는 모든 수에 대해서 중복되는 수로 구성되어 있는지를 조사하였지만 여지없이 TLE .. OTL

그러다 해결책이 떠올랐다.

이 문제는, 10개의 숫자 중 n개의 수를 중복 없이 뽑는 문제와 비슷해보인다. (순열..!!)

nPr = n! / (n-k)! (n개의 수에서 k개를 중복없이 뽑는 경우의 수)

그래서 해결책을 두 부분으로 나눌 수 있었다.

1) 순열을 이용해서 몇 자리 수인지 결정. n번째 수가 2자리 수인가? 3자리수인가?를 결정 하는 것이다.

만약 정답이 3자리 수(100 < n < 1000)라면, 이 수는 적어도 10개의 수 중 2개를 뽑는 방법의 가지수보다는 클것이다.

여기서는 처음자리에 0이 올 수 없으므로, 첫째 자리 수를 뽑을 때는 그 경우가 9가 된다.

2) 자리수가 결정되면 정답에 해당하는 수를 결정한다. 

처음에는 자리수에 해당하는 모든 수에 대해 유효성을 검사하는 방법을 생각해보았으나, 

그것보다는 직접 repeatless number를 추출해내는 것이 빠르겠다는 판단이 섰다. 이 부분은 재귀로 구현했다.

[출처] [AOJ 문제] Repeatless Numbers|작성자 DevMoon

코드: https://github.com/xgate/algospot/blob/master/NUM_OF_CASE/REPEATLESS.cpp