240211 [BOJ/백준] 11727. 2 x n 타일링 2

 

11727번: 2×n 타일링 2 (acmicpc.net)

11727번: 2×n 타일링 2

---

입력 코드

첫번째 입력

def f(n):
    if n == 1:
        return 1
    elif n == 2:
        return 3
    else:
        return f(n-2)*2 + f(n-1)


data = int(input())
result = f(data) % 10007
print(result)

 

결과

피보나치 수열을 함수로 썼더니 시간초과가 됐다.

---

두번째 입력

def tile(n):
    f = [0]*(n+1)
    f[1] = 1
    f[2] = 3
    for i in range(3, n+1):
        f[i] = f[i-2]*2 + f[i-1]
    return f[n]


data = int(input())
result = tile(data) % 10007
print(result)

 

결과

 

런타임 에러...ㅜㅜ f의 범위를 n+1로 해서 인덱스 에러가 났다.

---

세번째 입력

n = int(input())

f = [0]*(1001)

f[1] = 1
f[2] = 3

for i in range(3, n+1):
    f[i] = f[i-2]*2 + f[i-1]

print(f[n] % 10007)

 

결과

---

처음에 피보나치 수열로 함수를 짰을 때는 중복되는 데이터가 많음에도 그 함수를 다 계산해야해서 시간초과라는 결과를 얻었다. 그래서 다음으로 피보나치수열에서 많이 중복되는 데이터들을 저장하는 메모이제이션을 이용한 DP를 활용하여 코드를 짰다. DP에서 활용할 공간을 n+1로 주었더니 n이 1일 경우에 f(2)에 넣을 공간이 없어서 인덱스 에러가 났다. 그래서 입력값이 1이상 1000이하라는 내용으로 공간을 1001로 주었더니 문제를 해결할 수 있었다.