역시나 처음에 조합부터 떠오른 1인..
하지만 시간 초과 뜰 게 뻔해서
dp로 다시 방향을 바꾸었다!
이 문제는 피보나치 수열과 매우 유사하다.
n=1일때 1개
n=2일때 2개
n=3일때 3개 (1+2)
n=4일때 5개 (2+3)
dp[n]=dp[n-1]+dp[n-2]
그래서 간단하게 답을 도출해낼 수 있었다.
정답코드는 아래와 같다
n=int(input())
dp=[0] * 1000001
dp[1]=1
dp[2]=2
for i in range(3,n+1):
dp[i]=(dp[i-1]+dp[i-2])%15746
print(dp[n])
위 코드 같은 경우에는 시간이 473ms가 떠서
더 좋은 방식이 있나 찾아봤더니
행렬곱셈을 이용하여 피보나치 수열을 하게 되면
더 빠르게 값이 도출된다는 것을 알게 되었다.
def solve(n):
if n == 1:
return mul(A, 0)
if n % 2 == 1:
return mul(solve(n - 1), 1)
return mul(solve(n // 2), 2) # n이 2의 제곱일 경우, n=16이면, solve(8),k=2, [행렬]^8 * [행렬]^2
n=4일 경우
mul(solve(2),2)
solve(2) -> mul(solve(1),2)
solve(1) -> mul(A,0) -> A
mul(A,2) -> (2,1,1,1)
mul((2,1,1,1),2) -> (5,3,3,2)
print(a[0]) = 5
n=5일 경우
mul(solve(5-1),1)
solve(4) -> mul(solve(2),2)
solve(2) -> mul(solve(1),2)
solve(1) -> mul(A,0) -> A
mul(A,2) -> (2,1,1,1)
mul((2,1,1,1),2) -> (5,3,3,2)
mul(5,3,3,2),1) -> (5,3,3,2) * (1,1,1,0) -> (8,...)
print(a[0]) = 8
def mul(a, k):
if k == 1:
b = A
elif k == 2:
b = a
else:
b = B
return (
(a[0] * b[0] + a[1] * b[2]) % 15746,
(a[0] * b[1] + a[1] * b[3]) % 15746,
(a[2] * b[0] + a[3] * b[2]) % 15746,
(a[2] * b[1] + a[3] * b[3]) % 15746
)
k=1이면, > A^5=A^4*A^1 > A를 곱해주는 작업 (거듭제곱x)
k=2이면, > 거듭제곱해주는 과정 (곱셈의 연산수를 줄여주는 작업)
k=1도 아니고 2도 아닐 때 > 그냥 B를 곱해준다 (값의 변화 없음)
A, B = (1, 1, 1, 0), (1, 0, 0, 1)
n=int(input())
def mul(a, k):
if k == 1:
b = A
elif k == 2:
b = a
else:
b = B
return (
(a[0] * b[0] + a[1] * b[2]) % 15746,
(a[0] * b[1] + a[1] * b[3]) % 15746,
(a[2] * b[0] + a[3] * b[2]) % 15746,
(a[2] * b[1] + a[3] * b[3]) % 15746
)
A, B = (1, 1, 1, 0), (1, 0, 0, 1)
def solve(n):
if n == 1:
return mul(A, 0)
if n % 2 == 1:
return mul(solve(n - 1), 1)
return mul(solve(n // 2), 2) # n이 2의 제곱일 경우, n=16이면, solve(8),k=2, [행렬]^8 * [행렬]^2
return 안에 있는 건 행렬 곱셈 진행 과정
A=[a1 a2]
[a3 a4]
B= [b1 b2]
[b3 b4]
A*B=
[a1*b1+a2*b3 a1*b2+a2*b4]
[a3*b1+a4*b3 a3*b2+a4*b4]
'여니의 취준 준비 > 코딩테스트 (Python)' 카테고리의 다른 글
[n11655] ROT13 in python (0) | 2021.10.18 |
---|---|
[n1058] 친구 in python (0) | 2021.10.15 |
[n1026] 보물 in python (0) | 2021.10.13 |
[n1021] 회전하는 큐 in python (0) | 2021.10.13 |
[n1094] 막대기 in python (0) | 2021.10.12 |