프로그래머스 - 산 모양 타일링

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

프로그래머스

 

1. 2024 KAKAO WINTER INTERNSHIP 문제

타일링 문제는

항상 피보나치와 비슷하게 풀었던 경험이 있었다.

이번에도 몇 가지 테스트케이스를 만들어 수들의 연관성을 찾을 수 있었다.

 

[0] = 3     
[1] = 4    
[0, 0] = 8 
[0, 1] = 11
[1, 1] = 15
[0, 0, 0] = 21

 

도출한 테스트케이스만으로는 유추하기 힘들어 규칙성도 파악하기로 했다.

 

 

해당 사진을 예시로 설명하겠다. 

[1,1,0,1]이 input이다.

 

 

 

 

[1,1,0]에서 빨간색을 추가하면 [1,1,0,1]이다.

[1,1,0]의 답은 41이 나온다.

빨간색 삼각형이 붙었을 때 경우의 수를 생각해 보면

41 x 3 = 123이라는 숫자가 나온다.

 

만약  빨간색 삼각형이 2칸 붙는 경우 즉 [0]이 추가되는 경우는

곱하기 2를 해준다.

 

 

여기서 끝이 아니라 몇 가지의 경우의 수를 생각해야 한다.

 

파란색 삼각형일 때의 총경우의 수까지 계산을 해주어야 한다.

이것은 구조적으로 [1,1,0] - [1,1]의 경우의 수와 같다.

[1,1,0] - [1,1] = 26이다.

 

즉 답이 123 + 26 = 149가 나온다.

 

이를 수식으로 표현하면

 

[1,1]       = [1] * 3 + [1] - 1                    = 15
[1,1,0]    = [1, 1] * 2 + ([1,1] - [1])         = 41
[1,1,0,1] = [1,1,0] * 3 + ([1,1,0] - [1,1]) = 149

 

 

 

def solution(n, tops):
    dp = [1]
    if tops[0] == 1:
        dp.append(4)
    else:
        dp.append(3)
    for i in range(1, len(tops)):
        if tops[i] == 1:
            dp.append(dp[i] * 3 + (dp[i] - dp[i - 1]))
        else:
            dp.append(dp[i] * 2 + (dp[i] - dp[i - 1]))
    return dp[-1]%10007