프로그래머스 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

입출력 예 설명

입출력 예 #1
다음과 같이 5가지 방법이 있다.

나의 무지성 풀이

• 내가 코딩하는 순서대로 적어보기
• 처음엔 도형 그리기 문제라고 생각했다가 그려보니까
• "합이 n인 1과 2의 순서 조합"을 찾는 문젠가?
  • n = 4
    • n = 1+1+1+1
    • n = 1+1+2
    • n = 1+2+1
    • n = 2+1+1
    • n = 2+2

• 무지성 코딩 가즈아!
• 혹시 n이 4보다 작으면 그냥 리턴해버려.
• 결과는 ... 꺼져... ㅋㅋㅋ

• 어떻게 짤지 고민하면서 이런 저런 생각해보고...
• 그냥 내 머리속에서 내가 푸는 방식을 코딩한다고 생각
• 아니 근데 1, 2를 섞어서 순열을 만들면 합이 넘어가는지 체크해야하고...

• 아무 생각없이 계속 1과 2 조합으로 계속 만들어보니까...
• 어우 어질 어질하다.

n -> result	조합
1 -> 1	(1) = 1
2 -> 2	(1,1) = 1 (2) = 1
3 -> 3	(1,1,1) = 1 (1,2) = 2
4 -> 5	(1,1,1,1) = 1 (1,1,2) = 3 (2,2) = 1
5 -> 8	(1,1,1,1,1) = 1 (1,1,1,2) = 4 (1,2,2) = 3
6 -> 13	(1,1,1,1,1,1) = 1 (1,1,1,1,2) = 5 (1,1,2,2) = 6 (3+2+1) (2,2,2) = 1
7 -> 21	(1,1,1,1,1,1,1) = 1 (1,1,1,1,1,2) = 6 (1,1,1,2,2) = 10 (4+3+2+1) (1,2,2,2) = 4
8 -> 34	(1,1,1,1,1,1,1,1) = 1 (1,1,1,1,1,1,2) = 7 (1,1,1,1,2,2) = 15 (5+4+3+2+1) (1,1,2,2,2) = 10 (4+3+2+1) (2,2,2,2) = 1

• 이거 뭔가 규칙이 있는데...
  • 조합의 갯수가 f(n) = f(n-1) + f(n-2) 같은 규칙이 있네?
  • 근데 조합이 점점 많아지는데... 라고 생각했는데 result 자체가 수열이었네?
  • 1 삐져나오는 것 때문에 1 어떻게 처리하냐 싶었는데, 저 1이 삐져나오는게 아니라 f(n-2)에서 1 더하는 거라서 그냥 피보나치 수열이 되어버렸다.

• 안되잖아?

• 테스트 케이스만 통과한 소스를 바로 실행했으니...
• 잘보니까 a,b 반대로 써놓고, n에 3을 빼버렸네?
• 결과값도 100...007로 나눈 나머지를 리턴해야되는데 빠트림.

def solution(n):
    a, b = 2, 3
    n -= 2
    for i in range(n):
        c = a + b
        a, b = b, c
    return a % 1000000007

• 수정하고 나니 잘 된다.
• 시간이 너무 빨리 간다. 벌써 1시간 넘게 걸렸다.
• 이거랑 비슷한 문제가 3 x n 타일링이라는 문제가 있던데 그것도 비슷할 것 같다. 바로 다음에 풀어봐야지

정확성  테스트
테스트 1 〉	통과 (0.78ms, 10.2MB)
테스트 2 〉	통과 (0.09ms, 10MB)
테스트 3 〉	통과 (0.69ms, 10.2MB)
테스트 4 〉	통과 (2.12ms, 10.1MB)
테스트 5 〉	통과 (0.07ms, 10.1MB)
테스트 6 〉	통과 (0.88ms, 10.3MB)
테스트 7 〉	통과 (0.07ms, 10.2MB)
테스트 8 〉	통과 (1.19ms, 10.1MB)
테스트 9 〉	통과 (0.59ms, 9.97MB)
테스트 10 〉	통과 (2.33ms, 10MB)
테스트 11 〉	통과 (0.74ms, 10.1MB)
테스트 12 〉	통과 (0.17ms, 10.1MB)
테스트 13 〉	통과 (0.27ms, 10.3MB)
테스트 14 〉	통과 (0.43ms, 10.2MB)

효율성  테스트
테스트 1 〉	통과 (5.03ms, 10.1MB)
테스트 2 〉	통과 (9.52ms, 9.92MB)
테스트 3 〉	통과 (4.48ms, 10MB)
테스트 4 〉	통과 (3.50ms, 10.1MB)
테스트 5 〉	통과 (14.83ms, 10.3MB)
테스트 6 〉	통과 (27.54ms, 10.3MB)

고수의 풀이

• 깔끔하다. 나처럼 삽질 안하고 바로 푼 듯 ㅡ.ㅡ... 멋져부러...

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