(프로젝트 오일러 113번 문제입니다.)
숫자를 왼쪽부터 오른쪽으로 읽어나갈 때, 오른쪽에 나오는 숫자가 왼쪽 숫자보다 작지 않다면 그 수를 증가수라고 합시다. 예를 들어 134468은 증가수입니다. 마찬가지로 오른쪽에 나오는 숫자가 왼쪽 숫자보다 크지 않다면 그 수를 '감소수'라고 합시다. 66420은 감소수입니다. 증가수도 감소수도 아닌 나머지 수들은 오락가락수라고 하겠습니다. 예를 들어 155349는 오락가락수입니다.
수가 커질수록 오락가락수일 가능성은 높아집니다. 1,000,000 미만의 수 중 12,951개, 10^10 미만에서는 277,032개만이 증가수이거나 감소수입니다.
10^100(구골) 미만의 자연수들 중에 오락가락수가 아닌 수는 모두 몇 개입니까?
14개의 풀이가 있습니다.
python3로 작성했고, 컴파일러는 repl.it이라는 웹 컴파일러를 사용했습니다.
def factorial(n):
"""
어떤 수의 계승을 구하는 메소드
"""
if n < 1: return 1
rst = 1
for i in range(1, n+1):
rst *= i
return rst
def P(n, k):
"""
n개의 요소 중 k개의 요소를 뽑아 순열을 만드는 경우의 수를 구하는 메소드
"""
return factorial(n) // factorial(n-k)
def C(n, k):
"""
n개의 요소 중 k개의 요소를 뽑아 조합을 만드는 경우의 수를 구하는 메소드
"""
return P(n, k) // factorial(k)
def H(n, k):
"""
n개의 요소 중 k개의 요소를 뽑아 중복조합을 만드는 경우의 수를 구하는 메소드
"""
return C(n+k-1, k)
def func(n):
"""
10^n 미만의 자연수 중에서 오락가락 수가 아닌 수의 개수를 구하는 메소드
"""
increase, decrease = 0, 0
for i in range(1, n+1):
for j in range(1, 9+1):
increase += H(j, i-1)
for i in range(1, n+1):
for j in range(2, 10+1):
decrease += H(j, i-1)
return increase + decrease - 9*n
print(func(6))
print(func(10))
print(func(100))
# 실행결과
12951
277032
51161058134250
이 문제는 고등학교 때 배운 확률과 통계로 쉽게 풀 수 있습니다. 중복조합이라는 개념을 이용해서 푸는 문제였습니다.
Ruby
고등학교 수학 확률과 통계 중복조합, rcomb(n, k) = 오름수 + 내림수 - case(flat nums) - case(zeros)
comb = ->n,k { [k, n-k].min.times.reduce(1) {|a,e| a * (n-e) / (e+1) } }
rcomb = ->n { comb[n+9, 9] + comb[n+10, 10] - n*10 - 2 }
rcomb[100] #=> 51161058134250
Test
expect( rcomb[6] ).to eq 12951
expect( rcomb[10] ).to eq 277032
expect( rcomb[100] ).to eq 51161058134250
'''10**100까지 너무많아요. 10**6해봤더니 맞네요'''
Bong=0
for i in range(1,10**6): # 1부터 10**100미만의 수에 대하여
i=str(i) # i[0], i[1], ... , i[n]
n=len(i) # n= i의 자리수
j=0
if n>2: #3자리수부터 오락가락수 생성
trash=[] #숫자가 커지면 1, 작아지면 -1저장
while j< n-1:
if i[j]<i[j+1]: trash.append(1)
elif i[j]>i[j+1]: trash.append(-1)
j=j+1
if 1 in trash and -1 in trash: #만약 trash에 1과 -1이 같이 있으면
Bong+=1 #bong=오락가락수 갯수+1
break
ans=10**6-1-Bong #답=전체-오락가락수 갯수
print(ans)
자리수 별로 개수를 나눠서 구합니다.
import math
def num_combinations(n, r):
return math.factorial(n) // math.factorial(r) // math.factorial(n - r)
def num_combinations_with_replacement(n, r):
return num_combinations(n + (r - 1), r)
def incresing(n):
return num_combinations_with_replacement(9, n)
def decresing(n):
return num_combinations_with_replacement(10, n) - 1
def incresing_and_decresing(n):
return 9
print(sum(
incresing(n) + decresing(n) - incresing_and_decresing(n)
for n in range(1, 100 + 1)
))
def F(n): return 1 if n <= 1 else n * F(n - 1)
def P(n, k): return F(n) // F(n - k)
def C(n, k): return P(n, k) // F(k)
def H(n, k): return C(n + k - 1, k)
def inc(n): return H(10, n) - 1
def dec(n): return sum([H(10, i) - 10 for i in range(1, n + 1)])
def notbouncy(n): return inc(n) + dec(n)
print(notbouncy(6)) # 12951
print(notbouncy(10)) # 277032
print(notbouncy(100)) # 51161058134250
여기 참고
from math import factorial
def C(n,r):
return factorial(n)//(factorial(n-r)*factorial(r))
def H(n,r):
return C(n+r-1,r)
def getnnum(n):#n자리수까지
if(n==1):
return 9
num=0
for i in range(1,10):
num+=H(i+1,n-1)
num+=H(10-i,n-1)
num=num-1
num+=getnnum(n-1)
return num
print(getnnum(100))
중복조합+재귀함수
def demincrease(x):
a=list(str(x))
bool=[]
c=0
for i in range(0,len(a)-1):
bool.append(a[c]<=a[c+1])
c=c+1
if bool.count(False)==0:
return True
else:
return False
def demdecrease(x):
a=list(str(x))
bool=[]
c=0
for i in range(0,len(a)-1):
bool.append(a[c]>=a[c+1])
c=c+1
if bool.count(False)==0:
return True
else:
return False
def demorak(x):
if demincrease(x)==False:
if demdecrease(x)==False:
return True
else:
return False
else:
return False
score=10
for i in range(10,10**6):
if demorak(i)==False:
score=score+1
first=score
score=10
for i in range(10,10**10):
if demorak(i)==False:
score=score+1
second=score
score=10
for i in range(10,10**100):
if demorak(i)==False:
score=score+1
third=score
print("%d\n%d\n%d" % (first,second,third))
fct = lambda n: eval('(%s)'%'*'.join(str(i) for i in range(1, n+1))) if n!=0 else 1
h = lambda n, r: fct(n+r-1)//fct(r)//fct(n-1)
calc = lambda M: sum(sum(h(j, i-1) for j in range(2, 10+1)) + sum(h(j, i-1) for j in range(9, 1-1, -1)) for i in range(1, M+1)) - 9*M
if __name__ == '__main__':
for i in (6, 10, 100):
print(calc(i))
파이썬 3.6.2 64
저는 증가수를 가려내는 함수, 감소수를 가려내는 함수를 짜고 (굉장히 겹치는 코드가 많아 수정해야 하는데...좀 가르쳐주시면 좋겠습니다.)
증가수 가려내는 함수
def inc_checker(a):
str_a = str(a)
for i in range(len(str_a)):
if i != len(str_a)-1:
if str_a[i] > str_a[i+1]:
return 'False'
break
elif str_a[i] < str_a[i+1]:
continue
else:
continue
else:
return 'True'
감소수를 가려내는 함수
def dec_checker(a):
str_a = str(a)
for i in range(len(str_a)):
if i != len(str_a)-1:
if str_a[i] < str_a[i+1]:
return 'False'
break
elif str_a[i] > str_a[i+1]:
continue
else:
continue
else:
return 'True'
for문을 활용한 counting
count = 0
for i in range(10**6):
if i != (10**6)-1:
if inc_checker(i) == 'True' or dec_checker(i) == 'True':
count += 1
else:
continue
else:
print(count)
6일때는 돌아가는데 10일때와 100일 때는 커널이 죽어서... 일단 6일 때는 12,951이 나옵니다.
def num():
m=0
n=0
up=0
down=0
ran=0
orag=10**100
for p in range(0,orag):
j=len(str(p))
cal=str(p)
m=0
n=0
for k in range(1,j):
if cal[k] < cal[k-1]:
m=0
break
else:
m=1
for k in range(1,j):
if cal[k] > cal[k-1]:
n=0
break
else:
n=1
if m==1:
up+=1
if n==1:
down+=1
if m==0 and n==0:
ran+=1
print(up)
print(down)
print(orag-ran)
//본문에서는 1~9까지를 오락가락수로 본거같은데 전 어딘지모르겠네요 제코드는 up에 포함시켰습니다~
def cnt_inc_num(n):
cnt = [*range(9,0,-1)]
ret = 9 + sum(cnt)
for _ in range(n-2):
cnt = [sum(cnt[i:]) for i in range(9)]
ret += sum(cnt)
return ret
def cnt_dec_num(n):
cnt = [*range(1,11)]
ret = sum(cnt[1:])
for _ in range(n-2):
cnt = [sum(cnt[:i+1]) for i in range(10)]
ret += sum(cnt[1:])
return ret
cnt_incNdec_num = lambda n: cnt_inc_num(n) + cnt_dec_num(n) - 9*(n-1)
for n in [6, 10, 100]: print(f'10^{n}', cnt_incNdec_num(n), sep=': ')
10^6: 12951
10^10: 277032
10^100: 51161058134250
제 컴퓨터 에선 10^9 까지가 한계네요
combn.cal <- function(n, r){
nCr <- factorial(n) / factorial(n - r) / factorial (r)
return(nCr)
}
len_exp <- 6
non_lunatic <- 0
for (i in 1:len_exp){
if ((i - 1) > 9){
for (j in 1:9){
non_lunatic <- non_lunatic + combn.cal(9, j) * combn.cal(i - 1, j - 1)
}
} else if ((i - 1) <= 9){
for (j in 1:i){
non_lunatic <- non_lunatic + combn.cal(9, j) * combn.cal(i - 1, j - 1)
}
}
if (i == 1){
next()
} else {
if ((i - 1) > 10){
for (j in 2:10){
non_lunatic <- non_lunatic + combn.cal(10, j) * combn.cal(i - 1, j - 1)
}
} else if ((i - 1) <= 10){
for (j in 2:i){
non_lunatic <- non_lunatic + combn.cal(10, j) * combn.cal(i - 1, j - 1)
}
}
}
}
num_cnt=range(1,pow(10,100))
nums=0
hig=0
lowe=0
mid=0
for num2 in num_cnt:
num=list(str(num2))
a = 0
cur = 0
cur2 = 0
for eight in num:
eight=int(eight)
if nums>=eight and a==1:
cur+=1
if nums<=eight and a==1:
cur2+=1
if cur2==len(str(num2))-1:
hig+=1
elif cur==len(str(num2))-1:
lowe+=1
else:
mid+=1
nums=eight
a=1
print("%s,%s,%s,%s"%(hig,lowe,mid,hig+lowe))
10^100 은 시간이 너무너무 오래걸리네요.. 효율적인코딩을 위해 수정작업이필요할거같습니다.
using System;
namespace solution
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("10^100(구골) 미만의 자연수들 중에 오락가락수가 아닌 수는 ?");
int k = 100;
double incNum = H(10, k) - 1; // 00000000 제외
double decNum = 0;
for (int i = 2; i <= k; i++)
decNum += (H(10, i) - 10); // 00,11,22, * * *, 99 위와 증복해서 제외
Console.WriteLine("\n {0}", incNum+decNum);
}
private static double H(int n, int k)
{
//int res = factorial(n + k - 1) / (factorial(n - 1) * factorial(k));
return factorial(n + k - 1) / (factorial(n - 1) * factorial(k));
}
private static double factorial(int su)
{
double v = 1;
for (int i = 1; i <= su; i++)
v *= i;
return v;
}
}
}