[프로그래머스 연습]2 X N 타일링 - Python3

문제

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

코딩테스트 연습 - 2 x n 타일링 | 프로그래머스

 

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한사항

• 가로의 길이 n은 60,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

 

 

입출력

n	result
4	5

 

알고리즘

def solution(n):
    if n == 1:
        return 1
    if n == 2:
        return 2

    a, b = 1, 2
    for i in range(3, n+1):
        a, b = b % 1000000007, a+b % 1000000007

    return b
   

n = 4
print(solution(n))

설명

문제를 다 보고 나면 한번에 느낌이 오지 않는다. 처음에 들었던 생각은, 점화식으로 풀어야 겠다고 생각했다. 그래서 n=5일 때까지의 결과값을 뽑아보고자 손으로 열심히 그려봤다. 그러고 보니까 피보나치 수열과 점화식이 똑같았다. 그래서 답은 매우 간단하게 위의 코드를 따라가면 된다. 

결과

 

후기

이런 문제가 참 어려운 것 같다. 어찌 풀어야 할 지 감도 잘 안온다. 그래서 n=1일때의 경우에 몇가지만 더하면 n=2일때의 경우를 만들 수 있고, n=2일때의 경우의 수에 몇 가지만 더하면 n=3일때의 경우의 수를 만들 수 있고, ... 이런 식인줄 알고 다 그려보니까 결국은 피보나치더라. 근데 사실 피보나치 맞는지 잘 모르겠어서 저 코드 짜고 제발 맞아라 하고 기도했다. 잘 모르겠으면 일단 처음 몇가지를 해보자는 교훈을 얻었다.