[프로그래머스 level3 2xn 타일링] 피보나치 수열 사용하기

 

이 문제는 피보나치 수열을 활용할 수 있다는 것만 알게 된다면 간단한 문제였다.

 

 

해결해야하는 문제는 다음과 같았다.

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

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

 

 

피보나치 수열은 이전의 값 두 개를 더하여 현재 값을 도출한다.

이 문제의 경우, 초반에 경우의 수를 그리면서 규칙을 찾아보았다.

 

 

개수 변화(편의상 4까지만 작성)

 

우선 1,2,3,5,...로 커지는 과정을 통해 피보나치 수열인가? 라는 의심이 먼저 들어서, 피보나치 수열로 코드를 작성하였는데 바로 통과가 되었다.

 

통과 후 왜 피보나치 수열로 이 문제가 해결이 가능한지 생각해보았다.

 

 

그림을 자세히 분석해보니 다음과 같은 규칙을 찾을 수 있었다.

규칙찾기

 

4개 때의 타일로 만들 수 있는 경우의 수는 2개의 타일로 만들 수 있는 것에서 2개의 타일을 더 붙여야되고, 3개 때 만들 수 있는 것에서 한 개의 타일이 더 늘어나야 한다.

 

(4개의 타일로 만들 수 있는 경우의 수) = (2개 때의 타일로 만들 수 있는 경우의 수) + (3개 때의 타일로 만들 수 있는 경우의 수)

==> 일반화시키면 다음과 같다.

f(n) = f(n-1)+f(n-2)

 

 

최종 코드는 다음과 같다.

def solution(n):
    answer = 1
    fib0 = 1
    fib1 = 1
    if n == 1 :
        return 1
    if n==2 :
        return 2
    for i in range(n-1):
        answer = fib1 + fib0
        answer = answer % 1000000007
        fib0 = fib1 % 1000000007
        fib1 = answer % 1000000007
    return answer

 

 

기존에 많이 사용하던 수학 개념을 이렇게 다시 사용하니 신기하고 좋은 경험이었다.💪💪

코드를 작성할 때 무슨 알고리즘을 써야할지 생각하는 연습을 길러야 겠다는 생각을 하였다.