Project Euler #172: Investigating numbers with few repeated digits

문제가 짧군요.

How many 18-digit numbers n (without leading zeros) are there such that no digit occurs more than three times in n?

18자리수중에 어느 한 숫자가 3번넘게 반복되지 않는 경우의 수를 구하랍니다.

난이도가 55%라(푼 문제중 60%가 최고난도) 쫄아가지고 보류해놨는데 알고보니까 쉬운 문제네요 ㅇㅅㅇ;;

일단 1)쓰이는 서로 다른 숫자의 갯수를 정했습니다. 모든 수가 3번씩 쓰일 경우, 6개의 서로 다른 숫자가 쓰일거고, 10개의 모든 한자리수가 쓰일수가 있겠죠.

2)각 숫자가 몇번 등장하는지를 구했습니다. n번(1,2,3)쓰이는 숫자의 갯수를 xn이라 하면 x1+x2+x3=k(k는 6부터 10), x1+2*x2+3*x3=18이 되겠죠. 이렇게 쓰이는 숫자의 종류와 각각 몇번쓰이는 질 알면 이 조합으로 몇개의 숫자가 만들어지는 지를 구했습니다. 이를 다 더합니다.

3)모든 수는 동등한 지위(말 표현이 이상하지만...)를 가지고 있으므로 1이 앞에 올 경우의 수나 2가 앞에 올 경우의 수나 다 같습니다. 이때 0이 앞에 올 경우만 빼주면 되니까 2에서 구한 경우의 수에 9/10을 곱해줍니다.

이렇게 코드를 짜면..

import math,time starttime=time.time() def casecal(x1,x2,x3):#n in xn is the number of showing up cases=[x1,x2,x3] answer=1 ini=10 answer*=(math.factorial(10)/math.factorial(sum(cases))/math.factorial(ini-sum(cases))) ini=sum(cases) for i in cases: answer*=(math.factorial(ini)/math.factorial(i)/math.factorial(ini-i)) ini-=i answer*=(math.factorial(18)/6**x3/2**x2) return answer prob172answer=0 for k in range(6,11):#k refers to distinguishable digit in 18-digit number. for x in range(max(-18+2*k,0),int((3*k-18)/2)+1): prob172answer+=casecal(x,3*k-18-2*x,-2*k+x+18) prob172answer=round(prob172answer*0.9) print((prob172answer)) endtime=time.time() print('Elasped time is '+str(int(1000*(endtime-starttime)))+'ms')

16ms 정도 걸리네요