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

문제

---

• 산 모양 타일링 (LV3)

산 모양 타일링

아랫변의 길이가 n+1인 산 모양의 타일에서 정삼각형 타일과 마름모 타일을 통해서 해당 산 모양의 타일을 빈틈없이 모두 채우는 경우의 수를 구하는 문제였다.

내 코드

---

dp를 활용하면 문제를 풀 수 있을 것 같아서 해당 방식으로 접근해보았다.
정해진 특정 부분만 위쪽에 타일이 붙어서 해당 부분을 고려하는게 어려웠다.
위쪽에 타일이 존재하는 경우에만 따로 구분하여서 고려해주었다.
어떤 식으로 구현해야할지 생각하는 것은 어려웠지만 코드로 나타내니 생각보다 간단하게 풀 수 있었다.

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