아이테킨의 끄적끄적

# 2193번 : 이친수 # 재귀방법으로 피보나치 수열을 만들면 시간복잡도가 크기 때문에 시간초과가 난다. # tablatoin 방법으로 만들면 시간면에서 훨 효율적이다. n = int(input()) table = [0]*91 table[1] = 1 table[2] = 1 for i in range(3,n+1): table[i] = table[i-1] + table[i-2] print(table[n]) n=1 : 1 n=2 : 1 n=3 : 2 n=4 : 3 n=5 : 5 n=6 : 8 ... 처음엔 그냥 숫자들을 적어보다 보니 규칙을 발견할 수 있었다. 피보나치 수열과 같은 규칙이었다. 재귀방법으로 문제를 풀게 되면 시간복잡도가 커지고 시간초과가 난다 tablation방법으로 피보나치 수열을 구현하면..

예전에 공부할때 봤었던 이코테라는 책에 이 문제와 비슷한 유형이 있어서 쉽게 풀 수 있었다. 타일을 채우는 방법의 수를 구하는 문제인데 m(n) = m(n-1) + m(n-2)로 결국 피보나치 수열과 같다. 피보나치 수열은 DP의 대표적인 문제로 재귀와 반복문 둘다 풀이가 가능하고 둘다 알아놓으면 좋을 듯 하다. 이번에는 바텀업 방식으로 풀어보았다. 마지막에 10007로 나눈 나머지를 출력하는 것을 까먹으면 안된다 ㅠㅠ 이걸 놓쳐서 10분동안 "어.. 왜 안되지...??" 를 반복했다.ㅠㅠ # 11726번: 2xn 타일링 n = int(input()) m = [0]*1001 m[0] = 0 m[1] = 1 m[2] = 2 for i in range(3,n+1): m[i] = m[i-1] + m[i-2] ..