여니의 취준 준비/코딩테스트 (Python)

[n1904] 01타일 in python

여니's 2021. 10. 15. 14:32


역시나 처음에 조합부터 떠오른 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)

행렬 A에 B를 곱하면 항상 A의 값은 똑같음. 

 

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