파이썬 알고리즘 135번 | [백준 1904번] 01타일

135. 01타일

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>

n=int(input())
dp=[0]*1000001
dp[1]=1
dp[2]=2
if n==1 or n==2:
    print(n%15746)
else :
    for i in range(3,n+1):
        dp[i]=dp[i-1]+dp[i-2]
print(dp(n))

<다른 분의 풀이 or 내 틀린 풀이, 문제점>

출처 : 출처

런타임 에러, 메모리 초과 코드

def cnt(n):
    if n==1:
        return 1
    if n==2 :
        return 2
    if dp[n]!=0:
        return dp[n]
    dp[n]=cnt(n-1)+cnt(n-2)
    return dp[n]

if __name__=="__main__":
    dp=[0]*10000001
    num=(int(input()))
    print(cnt(num)%15746)

=>

import sys
sys.setrecursionlimit(10**6)

이거 붙이면 런타임에러는 멈춤, 근데 메모리 초과됨
-> top down으로 해서 그런가?
-> bottom up으로 변경

def cnt(n):
    if n==1 or n==2:
        return n
    a=1
    b=2
    for i in range(3,n+1):
        c=a+b
        a=b
        b=c
    return c
if __name__=="__main__":
    n=int(input())
    print(cnt(n)%15746)

얘도.. 아래애도 시간초과.. ㅠㅠ

def cnt(n):

    a=1
    b=2
    for i in range(3,n+1):
        c=a+b
        a=b
        b=c
if __name__=="__main__":
    n=int(input())
    if n==1 or n==2:
        print(n%15746)
    else :
        a=1
        b=2
        for i in range(3,n+1):
            c=a+b
            a=b
            b=c
        print(c%15746)

---

<다른 분의 코드>

출처 블로그

N = int(input())
dp = [0] * 1000001
dp[1], dp[2] = 1, 2
for i in range(3,N+1):
    dp[i] = (dp[i-1] + dp[i-2])%15746
print(dp[N])

<반성 점>

<배운 점>