[백준/Python] 11729번 2×n 타일링

---

문제

https://www.acmicpc.net/problem/11726

---

문제 이해

1x2 블럭을 채워넣는 경우의 수를 세는 문제이다.

n이 1인 경우부터 차례대로 세어나가고 있었다. n이 5인 경우를 구하고 있을 때 나는 눈치를 챘다.

이 문제는 피보나치 문제이구나!!

n	ans
1	1
2	2
3	3
4	5
5	8
6	13
7	21
8	34
9	55

---

문제 풀이(시간초과 : 피보나치 함수)

# 시간초과 : 재귀

n = int(input())

def fibo(x):

    if x == 1 or x == 2:

        return x

    else:

        return fibo(x-1) + fibo(x-2)

print(fibo(n))

 

나는 피보나치 문제니까 피보나치 함수를 만들어서 풀면 되겠지? 라고 생각하고 풀었지만 시간초과가 되었다.

백준 실버 문제에서는 웬만하면 시간초과 문제가 나타나는 것 같다.

그래도 알고리즘을 하나씩 알아가고 있다!!

---

문제풀이(정답 : 다이나믹 프로그래밍(DP))

n = int(input())

dp = [0] * (n+1)

for i in range(n+1):

    if i == 1:

        dp[1] = 1

    elif i == 2:

        dp[2] = 2

    else:

        dp[i] = dp[i-1] + dp[i-2]

print(dp[-1] % 10007)

 

시간초과 이슈로 다이나믹 프로그래밍을 사용했다.

나름 DP알고리즘은 익숙해져서 쉽게 풀 수 있었다.

 

+ 마지막 출력 조건 확인하자!!
이번 문제에서는 10007로 나눈 나머지 값을 출력하는 건데 그걸 안해서 틀렸다가 문제를 다시 읽고 깨달았다.