[알고리즘] 백준 11726 : 2×n 타일링 - S3

eternal moment·2023년 5월 13일
0

2023.05.14 풀이

  • 먼저 재귀로 접근 -> 시간초과
def dp(n):
    if n==1:
        return 1
    elif n==2:
        return 2
    else:
        return dp(n-1)+dp(n-2)
  • 반복문으로 접근 (풀이참고)
n=int(input())
if n<3:
    print(n%10007)
else:
    a,b=1,2
    for _ in range(n-2):
        a,b=b,a+b   
    print(b%10007)

2023.05.25 풀이

import sys
input=sys.stdin.readline

n=int(input())
d=[0]*1001

d[0]=1
d[1]=2
for i in range(2, n):
    d[i]=d[i-1]+d[i-2]

print(d[n-1]%10007)
  • d[0]*n 이면 런타임에러남


다른 풀이

1

n = int(input())

dp = [0]*1001
dp[0]
dp[1] = 1, 1
for i in range(2, 1001):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[n]%10007)

2

n = int(input())
arr = [0, 1, 2]

for i in range(3, n+1):
    arr.append(arr[i-1] + arr[i-2])

print(arr[n] % 10007)

3
n=int(input())
dp=[0]*(n+1)
for i in range(1,n+1):
    if i==1:
        dp[i]=1
        continue
    elif i==2:
        dp[i]=2
        continue
    dp[i]=dp[i-2]+dp[i-1]

print(dp[n]%10007)
  • 생각했던거랑 가장 근접했던 풀이

check point

  • 1, 2일때를 정해놓고, 3일때부터 반복문 - 재귀랑 같은 점화식으로

0개의 댓글