Programmers - 2*n 타일링 (Python3)

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

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

 

1. 문제설명

다음과 같은 2*n 평면을 1*2타일로 채운다

 

위와같이 여러가지 경우의 수가 생길 것 이다. 

이때, 가로의 길이가 n인 타일을 채우는 경우의 수를 구하면 된다.

 

 

 

 

2. 아이디어

채우는 1*2타일의 크기가 달라지는 것이 아니기 때문에, 가로길이만 신경쓰면 된다.

n이 2일경우부터 살펴보면

1. n = 2일 때,  2 / 11 (2개)
2. n = 3일 때, 12 / 21 / 111 (3개)
3. n = 4일 때, 22 / 112 / 121 / 211 / 1111 (5개)
4. n = 5일 때, 221 / 212 / 122 / 2111 / 1211 / 1121 / 1112 / 11111 (8개) 

매우 충격적이게도(?) 피보나치 수열로 풀린다.....

 

다만, 

1. 효율성테스트를 위해 재귀대신 반복문으로, 

2. 1000000007 로 나눈 나머지를 return 해야한다.

 

 

3. 코드

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

왜 3단계인지 알수없는 문제였다.