#문제 : 주어진 자연수 n에 대해, 다음의 함수 Ans(n)의 시간 복잡도는 어떻게 될까?
#n개의 주사위의 합을 python 코드로 보고 대학교 1학년 수준의 간단한 컴퓨터 공학적인 문제를 풀어보자.
#대충 목표는 임의의 자연수 n에 대해, Ans(n)=[ ( k , N) | k는 자연수, 3n≤k≤6n , N은 n개의 주사위를 던졌을 때 눈의 수의 합이 k가 되는 경우의 수} 라는 함수 Ans 를 정의하는 것이다. (최적화는 신경 쓰지 말자. 나는 멍청하기 때문에 최적화 같은 거 잘 못한다. 더 빠른 O(??)로 구할 수 있는 코드 있으면 알려주길 바란다. 혹시나 해서 말하는데, O(2n)=O(n)으로 볼 테니, "3n인 경우는 그냥 확인하지 말고 경우의 수가 1개라고 하면 된다." 라고 하는 건 O(1)을 목표로 하는 게 아니면 의미 없다.)
def Cart(a, b) :
B=[]
for i in a:
for j in b:
B.append(i+j)
return B
# Cart 함수는 Cartesian product(데카르트 곱)의 줄임말로, 두 집합 A, B에 대해 A×B 를 반환하는 함수이다.
def Ans(n) :
def f(L, k): #함수 f는 튜플의 list인 L과 자연수 k가 있을 때, L의 원소(튜플) 중에 성분들을 다 더했을 때 k가 나오는 경우의 수를 구한다.
a=0
for i in L:
b=0
for j in range(len(i)):
b=b+i[j]
if b==k:
a=a+1
return a
A=[(1,), (2,), (3,), (4,), (5,),(6,)] #A를 튜플들의 list로 만드는 게 Cart 함수 쓸 때 편하다.
B=A.copy()
C=[]
for i in range(1, n):
B=Cart(B, A)
for j in range(n, 6*n+1):
C.append((j, f(B, j)))
return C
"""
실행 결과 :
Ans(1)==[(1, 1), (2, 1), (3, 1), (4, 1), (5, 1), (6, 1)] 1~6이 나오는 경우의 수는 다 동일하다.
Ans(2)==[(2, 1), (3, 2), (4, 3), (5, 4), (6, 5), (7, 6), (8, 5), (9, 4), (10, 3), (11, 2), (12, 1)] 7이 가장 많이 나온다.
Ans(3)==[(3, 1), (4, 3), (5, 6), (6, 10), (7, 15), (8, 21), (9, 25), (10, 27), (11, 27), (12, 25), (13, 21), (14, 15), (15, 10), (16, 6), (17, 3), (18, 1)] 10과 11이 가장 많이 나온다.
Ans(4)==[(4, 1), (5, 4), (6, 10), (7, 20), (8, 35), (9, 56), (10, 80), (11, 104), (12, 125), (13, 140), (14, 146), (15, 140), (16, 125), (17, 104), (18, 80), (19, 56), (20, 35), (21, 20), (22, 10), (23, 4), (24, 1)] 14가 가장 많이 나온다.
Ans(5)==[(5, 1), (6, 5), (7, 15), (8, 35), (9, 70), (10, 126), (11, 205), (12, 305), (13, 420), (14, 540), (15, 651), (16, 735), (17, 780), (18, 780), (19, 735), (20, 651), (21, 540), (22, 420), (23, 305), (24, 205), (25, 126), (26, 70), (27, 35), (28, 15), (29, 5), (30, 1)] 17과 18이 가장 많이 나온다.
그리고 보면 알겠지만, Ans의 결과는 경우의 수를 기준으로 볼 때 중간 지점을 기준으로 대칭적이고, n이 2 이상의 정수면 3.5*n에 가까울수록 경우의 수가 많아진다.
여기서 정말로 https://arca.live/b/maths/1148367?p=1 문제의 답을 정확하게 도출하고 싶으면, tuple의 리스트에서 두 번째 성분이 최댓값을 갖는 원소들을 찾아 주면 된다.
"""
