프로그래머스 3 x n 타일링 역대급 어렵넼ㅋㅋ

2 x n이랑 비슷할 줄 알았는데 상상을 초월하는 어려움이 있다.

진짜 지금까지 푼 프로그래머스 레벨 2 문제 중에서 역대급 난이도 같다.

문제설명

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

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

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

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

제한사항

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

입출력 예

n	result
4	11

입출력 예 설명

입출력 예 #1

다음과 같이 11가지 방법이 있다.

나의 풀이

• 처음에는 2 x n 타일링 비슷하게 될 줄 알았는데, 순열 케이스가 너무 많았다.
• 그래서 힌트를 살짝 볼 수 밖에 없었다. 점화식을 공부해야됨.

[기본개념] 점화식

점화식이란?

• 수열에서 이웃하는 두항의 관계
  • 수열 = {an} = 1, 3, 5, 7, 9, 11, ...
  • 1항 = a1 = 1
  • n+1항 = an+1 = an + 2 {n=1,2,3,...}
• 기본 점화식 (단, f(n)은 상수, n차함수, 지수함수이며 c는 상수입니다)
  • an+1 = an + f(n)
  • an+1 = f(n) * an
  • an+1 = c * an + f(n)
• 변형점화식
  • an + α = bn
  • an+1 - an = bn
  • 1/an = bn

수열 만들기

• 점화식을 만들려면 먼저 수열을 만들어야 한다.
• 일단 n이 홀수면 가득 채울 수 없으므로 0을 리턴.
• 필요없엉. 테스트 전부 짝수임.

• 그리고 높이가 3이라 하나 가로로 눞혀야 해서 a,b,c 3종류로 순열을 만들어야 함.
• 글고 aa, bb인 경우 가운데를 눞히는 방식으로 1개씩 추가할 수 있음.
• aaa일 경우 2개 추가, aaaa인 경우 3개 추가, ...

• 그럼 이렇게 되나?
• 너무 많은데? 손으로 하는 건 포기.
• 피보나치도 아니고 뭐야...?

n : result	순열	추가
2 : 3   = 3**1	a, b, c
4 : 11   = 9 + 2   = 3**2 + 1x2	aa, ba, ca ab, bb, cb ac, bc, cc	(1) x 2 :  aa, bb
6 : 41   = 27 + 8 + 4   = 3**3 + 1x8 + 2x2	aaa, baa, caa aab, bab, cab aac, bac, cac aba, bba, cba abb, bbb, cbb abc, bbc, cbc aca, bca, cca acb, bcb, ccb acc, bcc, ccc	(2) x 2 : aaa, bbb (1) x 2 x 4 : baa, aab, aac, caa  abb, bba, bbc, cbb
8 : 153 = 81 + 72 = 3**4 + 1x12 + 2x16 + 3x6	aaaa, baaa, caaa aaab, baab, caab aaac aaba aabb aabc aaca aacb aacc abaa abab abac abba abbb, bbbb, cbbb abbc, ... ... accc, bccc, cccc	(3) x 2 x 3 : aaaa, bbbb (2) x 8 x 2 : baaa, aaab, aaac, caaa abbb, bbba, bbbc, cbbb (1) x 12 aaba, aabb, aabc, aaca, aacb, aacc bbab, bbaa, bbac, bbca, bbcb, bbcc baab, caac abba. cbbc 개많네...
10 : 571 = 243 + 328 =	aaaaa, bbbbb, ccccc	(4) x 2 (3) x 2 x 3 x 2 (2) x 8 x 2 x 3 (1) x 12 x ....
12 : 2131 = 729 + 1402 =	aaaaaa, bbbbbb, cccccc
14 : 7953 = 2187 + 5766 =	aaaaaaa, bbbbbbb, ccccccc

• n//2크기로 a,b,c 순열 만들고, a,b,c 원소 2개이상 붙은 애들을 뽑아서, 원소가 중복으로 붙은 갯수 최대값에 1 빼주고 팩토리얼 계산하면 그 값인데... 앞에서 만든 조합에 a,b,c 붙여서 조합이 어떻게 만들어지는지가 규칙.
• 이걸 찾는 코드를 짜려다가, 여기쯤에서 힌트를 보자. 머리가 한계다.
• 라고 봤더니 점화식 너무 쉬운... ㅡ.ㅡ;
  • 길이가 n인 타일링의 총 가짓수를 A(n) 이라고 하자
  • A(n)=3A(n-2)+2(A(n-4)+A(n-6)+A(n-8) . . .) 으로 둘수있다.
  • T: O(N2) , S: O(N)
  • 위 코드를 그냥 코드로옮기면 정답입니다.
• 이걸 보고 다시 위를 보니... 내가 잘못 생각했꾸나... 앞에걸 전부 더해서 2로 곱해주는 거였다니...
  • A(0) = 1
  • A(2) = 3A(0) = 3
  • A(4) = 3A(2) + 2(A(0)) = 3x3 + 2x1 = 11
  • A(6) = 3A(4) + 2(A(2)+A(0)) = 3x11 + 2x(3+1) = 33 + 8 = 41
  • A(8) = 3A(6) + 2(A(4)+A(2)+A(0)) = 3x41 + 2x(11+3+1) = 123 + 30 = 153
• 감사합니다. 살아났엉... 일단 맞나 확인!

# 오류 'RecursionError: maximum recursion depth exceeded'
import sys
sys.setrecursionlimit(10**5)

def solution(an):
    
    def f(n):
        if n < 0:
            return 0
        elif n == 0:
            return 1
        elif n == 2:
            return 3
        return 3*f(n-2) + 2*sum(f(n-i) for i in range(4, n+1, 2))
    
    return f(an)

• 영겁의 시간이 흐르고 ㅋㅋㅋ

정확성  테스트
테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)
테스트 13 〉	
테스트 14 〉

• 메모이제이션 방식으로 수정해보았으나... 실패.
• 뭐야 안되네 ㅡ.ㅡ;

import sys
sys.setrecursionlimit(10**5)

def solution(an):
    memo = {}
    memo[0] = 1
    memo[2] = 3
    memo[4] = 11
    
    def f(n):
        if n in memo:
            return memo[n]
        memo[n] = 3*f(n-2) + 2*sum(f(n-i) for i in range(4, n+1, 2))
        return memo[n]

    return f(an)

• 런타임 에러남.

정확성  테스트
테스트 1 〉	실패 (런타임 에러)
테스트 2 〉	실패 (런타임 에러)
테스트 3 〉	실패 (런타임 에러)
테스트 4 〉	실패 (런타임 에러)
테스트 5 〉	실패 (2.54ms, 10.4MB)
테스트 6 〉	실패 (런타임 에러)
테스트 7 〉	실패 (런타임 에러)
테스트 8 〉	실패 (런타임 에러)
테스트 9 〉	실패 (런타임 에러)
테스트 10 〉	실패 (런타임 에러)
테스트 11 〉	실패 (런타임 에러)
테스트 12 〉	실패 (런타임 에러)
테스트 13 〉	실패 (런타임 에러)
테스트 14 〉	실패 (런타임 에러)
효율성  테스트
테스트 1 〉	실패 (런타임 에러)
테스트 2 〉	실패 (런타임 에러)
테스트 3 〉	실패 (런타임 에러)
테스트 4 〉	실패 (런타임 에러)
테스트 5 〉	실패 (런타임 에러)
테스트 6 〉	실패 (런타임 에러)

• 재귀호출 안 쓰고 for문 돌려서 순서대로 계산해야 되나보다....
  • 이 넘두 런타임 에러남.

def solution(an):
    memo = {}
    memo[0] = 1
    memo[2] = 3
    memo[4] = 11
    
    for n in range(6, an+1, 2):
        memo[n] = 3*memo[n-2] + 2*sum(memo[n-i] for i in range(4, n+1, 2))

    return memo[an]

• 아... 바보다. ㅋㅋㅋ
• 리털할 때 나머지를 리턴하는 문제는 항상 여기서 시간을 소비한다.
• 담부턴 미리 리턴 값 옆에 % 1000000007 써놔야지.

def solution(an):
    memo = {}
    memo[0] = 1
    memo[2] = 3
    for n in range(4, an+1, 2):
        memo[n] = 3*memo[n-2] + 2*sum(memo[n-i] for i in range(4, n+1, 2))
    return memo[an] % 1000000007

정확성  테스트
테스트 1 〉	통과 (129.62ms, 10.3MB)
테스트 2 〉	통과 (190.78ms, 10.6MB)
테스트 3 〉	통과 (422.12ms, 10.8MB)
테스트 4 〉	통과 (503.37ms, 10.8MB)
테스트 5 〉	통과 (0.68ms, 10.2MB)
테스트 6 〉	통과 (73.85ms, 10.4MB)
테스트 7 〉	통과 (169.04ms, 10.4MB)
테스트 8 〉	통과 (366.74ms, 10.6MB)
테스트 9 〉	통과 (215.19ms, 10.5MB)
테스트 10 〉	통과 (68.36ms, 10.4MB)
테스트 11 〉	통과 (146.26ms, 10.6MB)
테스트 12 〉	통과 (35.41ms, 10.4MB)
테스트 13 〉	통과 (75.83ms, 10.3MB)
테스트 14 〉	통과 (73.72ms, 10.4MB)
효율성  테스트
테스트 1 〉	통과 (415.51ms, 10.7MB)
테스트 2 〉	통과 (418.13ms, 10.5MB)
테스트 3 〉	통과 (406.05ms, 10.8MB)
테스트 4 〉	통과 (414.27ms, 10.8MB)
테스트 5 〉	통과 (561.70ms, 10.7MB)
테스트 6 〉	통과 (388.69ms, 10.7MB)

• 그럼 재귀호출도 되는 거였고... 는 안되고 (시간초과)
• 재귀호출 메모이제이션 방식만 되는 거였다.

import sys
sys.setrecursionlimit(10**5)

def solution(an):
    memo = {}
    memo[0] = 1
    memo[2] = 3
    memo[4] = 11
    
    def f(n):
        if n in memo:
            return memo[n]
        memo[n] = 3*f(n-2) + 2*sum(f(n-i) for i in range(4, n+1, 2))
        return memo[n]

    return f(an) % 1000000007
    
정확성  테스트
테스트 1 〉	통과 (220.05ms, 11.3MB)
테스트 2 〉	통과 (334.00ms, 12MB)
테스트 3 〉	통과 (626.87ms, 12.3MB)
테스트 4 〉	통과 (727.99ms, 12.6MB)
테스트 5 〉	통과 (1.40ms, 10.4MB)
테스트 6 〉	통과 (152.36ms, 11.1MB)
테스트 7 〉	통과 (368.14ms, 11.8MB)
테스트 8 〉	통과 (639.78ms, 12.1MB)
테스트 9 〉	통과 (360.61ms, 12MB)
테스트 10 〉	통과 (131.92ms, 10.9MB)
테스트 11 〉	통과 (337.41ms, 11.7MB)
테스트 12 〉	통과 (126.12ms, 10.9MB)
테스트 13 〉	통과 (198.22ms, 11.1MB)
테스트 14 〉	통과 (156.27ms, 11.2MB)
효율성  테스트
테스트 1 〉	통과 (661.99ms, 12.3MB)
테스트 2 〉	통과 (676.00ms, 12.7MB)
테스트 3 〉	통과 (633.50ms, 12.6MB)
테스트 4 〉	통과 (647.55ms, 12.4MB)
테스트 5 〉	통과 (861.99ms, 12.9MB)
테스트 6 〉	통과 (637.42ms, 12.2MB)

• 결론은 뭐다?
  • 재귀호출 + 메모이제이션
  • for문 + 메모이제이션

다른 분들의 풀이

• 비슷한 방식인데, 리스트로 하면 접근 속도가 느려져서 좀 더 느리게 나오는 것 같다.

def solution(n):
    answer = 0
    dp=[0]*(n+5)
    dp[0]=1
    dp[2]=3
    dp[3]=0
    for i in range(4,n+1):
        dp[i]=(3*dp[i-2]+2*sum([dp[i-j] for j in range(4,n+1,2) if i-j>=0]))%(10**9+7)
    return dp[n]
    
정확성  테스트
테스트 1 〉	통과 (323.38ms, 10.2MB)
테스트 2 〉	통과 (433.67ms, 10.1MB)
테스트 3 〉	통과 (720.11ms, 10.3MB)
테스트 4 〉	통과 (728.25ms, 10.2MB)
테스트 5 〉	통과 (2.14ms, 10.3MB)
테스트 6 〉	통과 (168.99ms, 10.3MB)
테스트 7 〉	통과 (418.55ms, 10.1MB)
테스트 8 〉	통과 (696.55ms, 10.2MB)
테스트 9 〉	통과 (403.68ms, 10.3MB)
테스트 10 〉	통과 (134.42ms, 10.2MB)
테스트 11 〉	통과 (300.67ms, 10.3MB)
테스트 12 〉	통과 (112.97ms, 10.2MB)
테스트 13 〉	통과 (179.96ms, 10.2MB)
테스트 14 〉	통과 (159.80ms, 10.3MB)
효율성  테스트
테스트 1 〉	통과 (617.27ms, 10.1MB)
테스트 2 〉	통과 (664.34ms, 10.1MB)
테스트 3 〉	통과 (713.28ms, 10.2MB)
테스트 4 〉	통과 (673.38ms, 10.3MB)
테스트 5 〉	통과 (847.21ms, 10.1MB)
테스트 6 〉	통과 (641.23ms, 10.4MB)

• 리스트를 쓰려면 이렇게 써야 빨라진다.
  • dp.append()할 때 %1000000007로 나눠준다. 숫자가 작아지면 속도가 빨라진다.
  • 그리고 for문이 아니라 sum(dp[0:1])로 더 빠르게 가능.

def solution(n):
    dp = [1,0,3]
    for i in range(0, n-2):
        if i % 2 == 0:
            dp.append(0)
        else:
            dp.append((3 * dp[i + 1] + 2 * sum(dp[0:i]))% 1000000007)
    answer = dp[n]
    return answer
    
정확성  테스트
테스트 1 〉	통과 (12.89ms, 10.2MB)
테스트 2 〉	통과 (20.51ms, 10.3MB)
테스트 3 〉	통과 (56.07ms, 10.1MB)
테스트 4 〉	통과 (64.88ms, 10.1MB)
테스트 5 〉	통과 (0.17ms, 10.2MB)
테스트 6 〉	통과 (11.60ms, 10MB)
테스트 7 〉	통과 (29.75ms, 10.2MB)
테스트 8 〉	통과 (37.16ms, 10.2MB)
테스트 9 〉	통과 (28.25ms, 10.2MB)
테스트 10 〉	통과 (12.35ms, 10.3MB)
테스트 11 〉	통과 (16.18ms, 10.1MB)
테스트 12 〉	통과 (7.70ms, 10.1MB)
테스트 13 〉	통과 (8.19ms, 10.3MB)
테스트 14 〉	통과 (8.21ms, 10.2MB)
효율성  테스트
테스트 1 〉	통과 (29.99ms, 10.3MB)
테스트 2 〉	통과 (36.64ms, 10.2MB)
테스트 3 〉	통과 (34.63ms, 10.2MB)
테스트 4 〉	통과 (32.84ms, 10.2MB)
테스트 5 〉	통과 (42.98ms, 10.3MB)
테스트 6 〉	통과 (32.03ms, 10.2MB)

• 재귀호출했던 거 값만 나머지로 저장해보니까 더 빨라진다.

import sys
sys.setrecursionlimit(10**5)

def solution(an):
    memo = {}
    memo[0] = 1
    memo[2] = 3
    memo[4] = 11
    
    def f(n):
        if n in memo:
            return memo[n]
        memo[n] = (3*f(n-2) + 2*sum(f(n-i) for i in range(4, n+1, 2))) % 1000000007
        return memo[n]

    return f(an)
    
정확성  테스트
테스트 1 〉	통과 (148.17ms, 11.4MB)
테스트 2 〉	통과 (229.07ms, 11.9MB)
테스트 3 〉	통과 (412.43ms, 12.4MB)
테스트 4 〉	통과 (437.16ms, 12.2MB)
테스트 5 〉	통과 (1.25ms, 10.3MB)
테스트 6 〉	통과 (112.06ms, 11.2MB)
테스트 7 〉	통과 (205.96ms, 11.7MB)
테스트 8 〉	통과 (361.39ms, 12.1MB)
테스트 9 〉	통과 (244.50ms, 11.8MB)
테스트 10 〉	통과 (78.78ms, 10.8MB)
테스트 11 〉	통과 (170.68ms, 11.5MB)
테스트 12 〉	통과 (50.16ms, 10.8MB)
테스트 13 〉	통과 (102.50ms, 11.1MB)
테스트 14 〉	통과 (99.90ms, 11.3MB)
효율성  테스트
테스트 1 〉	통과 (431.02ms, 12.4MB)
테스트 2 〉	통과 (464.28ms, 12.4MB)
테스트 3 〉	통과 (455.27ms, 12.4MB)
테스트 4 〉	통과 (393.72ms, 12.3MB)
테스트 5 〉	통과 (540.58ms, 12.6MB)
테스트 6 〉	통과 (410.08ms, 12.4MB)

• for문 메모이제이션 방식도 나머지를 저장하니까 더 빨라진다.

def solution(an):
    memo = {}
    memo[0] = 1
    memo[2] = 3
    for n in range(4, an+1, 2):
        memo[n] = (3*memo[n-2] + 2*sum(memo[n-i] for i in range(4, n+1, 2))) % 1000000007
    return memo[an]
    
정확성  테스트
테스트 1 〉	통과 (66.58ms, 10.1MB)
테스트 2 〉	통과 (106.73ms, 10.3MB)
테스트 3 〉	통과 (191.57ms, 10.4MB)
테스트 4 〉	통과 (203.87ms, 10.3MB)
테스트 5 〉	통과 (0.54ms, 10.1MB)
테스트 6 〉	통과 (45.13ms, 10.1MB)
테스트 7 〉	통과 (94.73ms, 10.4MB)
테스트 8 〉	통과 (169.50ms, 10.2MB)
테스트 9 〉	통과 (109.42ms, 10.2MB)
테스트 10 〉	통과 (35.07ms, 10.2MB)
테스트 11 〉	통과 (77.40ms, 10.5MB)
테스트 12 〉	통과 (22.45ms, 10.2MB)
테스트 13 〉	통과 (46.06ms, 10.2MB)
테스트 14 〉	통과 (46.64ms, 10.2MB)
효율성  테스트
테스트 1 〉	통과 (204.12ms, 10.3MB)
테스트 2 〉	통과 (217.50ms, 10.3MB)
테스트 3 〉	통과 (211.68ms, 10.5MB)
테스트 4 〉	통과 (183.46ms, 10.3MB)
테스트 5 〉	통과 (227.46ms, 10.3MB)
테스트 6 〉	통과 (190.39ms, 10.3MB)

• 초고수. 이게 뭐지? 대박인데...

def solution(n):
    if n % 2:
        return 0
    front = back = 1
    for _ in range(n//2):
        front, back = back, (4*back - front) % 1000000007
    return back
    
정확성  테스트
테스트 1 〉	통과 (0.15ms, 10.1MB)
테스트 2 〉	통과 (0.23ms, 10.1MB)
테스트 3 〉	통과 (0.24ms, 10MB)
테스트 4 〉	통과 (0.27ms, 10.1MB)
테스트 5 〉	통과 (0.02ms, 10.1MB)
테스트 6 〉	통과 (0.20ms, 10.1MB)
테스트 7 〉	통과 (0.26ms, 10.2MB)
테스트 8 〉	통과 (0.47ms, 10MB)
테스트 9 〉	통과 (0.39ms, 10MB)
테스트 10 〉	통과 (0.14ms, 9.96MB)
테스트 11 〉	통과 (0.26ms, 10.1MB)
테스트 12 〉	통과 (0.10ms, 10.2MB)
테스트 13 〉	통과 (0.12ms, 10.1MB)
테스트 14 〉	통과 (0.24ms, 10MB)
효율성  테스트
테스트 1 〉	통과 (0.26ms, 10MB)
테스트 2 〉	통과 (0.27ms, 10.2MB)
테스트 3 〉	통과 (0.57ms, 10.1MB)
테스트 4 〉	통과 (0.29ms, 10.3MB)
테스트 5 〉	통과 (0.31ms, 10.1MB)
테스트 6 〉	통과 (0.28ms, 10.1MB)

• 이것도 점화식이 아니라 규칙 찾아서 풀었네

def solution(n):
    pa, pb, pc, a, b, c = 1, 0, 0, 0, 0, 2
    for _ in range(1, n):
        pa, pb, pc, a, b, c = a, b, c, (c + pa) % 1000000007, c, (b + a * 2) % 1000000007
    return a
    
정확성  테스트
테스트 1 〉	통과 (0.46ms, 10.1MB)
테스트 2 〉	통과 (0.57ms, 10.2MB)
테스트 3 〉	통과 (0.79ms, 10.2MB)
테스트 4 〉	통과 (0.84ms, 10.1MB)
테스트 5 〉	통과 (0.05ms, 10.2MB)
테스트 6 〉	통과 (0.38ms, 10MB)
테스트 7 〉	통과 (0.57ms, 10.1MB)
테스트 8 〉	통과 (0.72ms, 10.1MB)
테스트 9 〉	통과 (0.85ms, 10.2MB)
테스트 10 〉	통과 (0.34ms, 10.3MB)
테스트 11 〉	통과 (0.51ms, 10.1MB)
테스트 12 〉	통과 (0.27ms, 10.1MB)
테스트 13 〉	통과 (0.76ms, 10.2MB)
테스트 14 〉	통과 (0.38ms, 10.2MB)
효율성  테스트
테스트 1 〉	통과 (1.19ms, 10.1MB)
테스트 2 〉	통과 (1.06ms, 10.2MB)
테스트 3 〉	통과 (0.81ms, 10.1MB)
테스트 4 〉	통과 (0.71ms, 10.1MB)
테스트 5 〉	통과 (1.15ms, 10.2MB)
테스트 6 〉	통과 (1.07ms, 10.3MB)

• 아무튼 이걸 계기로 점화식 찾는 거 공부 좀 해야할 것 같고,
• 점화식을 더 간단하게 바꾸는 방법도 생각해봐야할 것 같고,
• 이런 순열 문제는 규칙을 찾아서 코드를 더 단순화 시킬 수 있는 방법을 찾아야 할 것 같다.