아방가르드 타일링 (181186번) - 프로그래머스 (Programmers)

https://school.programmers.co.kr/learn/courses/30/lessons/181186

프로그래머스

 

 

프로그래머스 - 아방가르드 타일링 (181186번)

 

난이도 : Lv 3

알고리즘 : Dynamic Programming (DP), Mathematics

풀이 소요 시간 : 150 mins

Time Complexity : O( N )

 

def solution(n):
    memo = [1, 1, 3, 10, 23, 62]
    if n <= 5:  return memo[n]
    four = [2, 2, 0]
    five = [2, 0, 0]
    six = [0, 0, 0]
    for i in range(6, n+1):
        cur = memo[-1] + 2*memo[-2] + 5*memo[-3]
        idx = (i-2)%3
        five[idx] += memo[1] << 1
        cur += five[idx]
        idx = (i-1)%3
        four[idx] += memo[2] << 1
        cur += four[idx]
        idx = i%3
        six[idx] += memo[0] << 2
        cur += six[idx]
        memo = memo[1:] + [cur]
    return memo[-1] % 1_000_000_007

 

경우의 수 찾아내기가 아주 어려운 문제였다.

특히 높이 4, 5 ,6 으로 만들 수 있는 조합을 찾는 데에 많은 시간이 걸렸다.

 

결과적으로 DP를 활용해서, O( N ) 만에 풀 수 있는 문제였다.

 

끈기를 갖고 가능한 모든 경우의 수를 찾아낸 다음,

점화식을 찾아내서 풀면 된다.

 

---

 

n에서 가능한 경우의 수를 F(n) 이라고 하면,

 

점화식

위와 같이 점화식이 나오게 된다.

 

여기서 (4, 5, 6) 부분은, dp를 통해 누적된 합을 기록해놔야 O(N) 으로 풀 수 있다.