프로그래머스 - LV3. 2*n 타일링

문제 

programmers.co.kr/learn/courses/30/lessons/12900

코딩테스트 연습 - 2 x n 타일링

 

코드

1) math모듈의 factorial 이용

from math import factorial

def solution(n):
    answer = 0
    tile_1 = n
    tile_2 = 0
    
    while tile_1 >= 0:
        if tile_1 == 0 or tile_2 == 0:
            answer += 1
        else:
            answer += factorial(tile_1 + tile_2) / factorial(tile_1) * factorial(tile_2)
        tile_1 -= 2
        tile_2 += 1
        
    return answer

factorial을 이용하니 타임에러됐다.

 

 

 

 

 

 

1) 피보나치 수열 이용

def solution(n):
	a,b = 1,1
	for i in range(n):
		a,b = b,a+b
	return a%1000000007

n = 1일 때, 전체 경우의 수는 1

n = 2일 때, 전체 경우의 수는 2

n = 3일 때, 전체 경우의 수는 3

n = 4일 때, 전체 경우의 수는 5

n = 3일 때, 전체 경우의 수는 8

문제의 결과들을 나열해 보니 피보나치 수열을 이용하면 간단할 것 같았다.

 

 

 

 

 

 

 

 

 

 

결론

이런 문제들은 재귀와 팩토리얼을 이용할 수도 있지만, 피보나치 수열을 이용한 것이 가장 간단하고 빠르므로 익혀둬야 겠다!

피보나치 관련 다른 문제

• 피보나치 수 : programmers.co.kr/learn/courses/30/lessons/12945