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

코데풀님의 블로그를 참고하면 사진으로 더욱 자세한 설명을 볼 수 있습니다.

😀요점

1. 한번의 모든 경우를 계산하려 하지 말고, n 번째 사다리꼴을 순회하며 누적하는 식으로 경우의 수 계산
2. dp 배열은 2차원 배열이며 n 번째 사다리꼴의 마지막 타일 도형을 계산함 [[삼각형으로 끝날 경우의 수, 마름모로 끝날 경우의 수]]
3. n-1 번째의 마지막 타일 도형이 무엇이냐에 따라 다음과 같은 공식이 성립함

   dp[n][0] = dp[n-1][0] * 2 + dp[n-1][1]
   dp[n][1] = dp[n-1][0] + dp[n-1][1]

😎풀이

function solution(n, tops) {
    const DIVIDER = 10007;

    // 첫 번째 위치에서 마지막 타일 모양에 따른 경우의 수 할당
    // 0: 삼각형, 1: 마름모
    const start = (tops[0]) ? [[3, 1]] : [[2, 1]];
    const dp = [...start, Array.from({length: n-1}, () => [0, 0])]

    for (let i = 1; i < n; i++) {
        // 이전 위치에서의 경우의 수를 가져옵니다.
        const [end_tri, end_dia] = dp[i - 1];

        if (tops[i] === 0) {
            // 현재 위치의 맨 위에 정삼각형이 없는 경우
            dp[i] = [(end_tri*2 + end_dia) % DIVIDER, (end_tri + end_dia) % DIVIDER];
        } else if (tops[i] === 1) {
            // 현재 위치의 맨 위에 정삼각형이 있는 경우
            dp[i] = [((end_tri + end_dia) * 2 + end_tri) % DIVIDER, (end_tri + end_dia) % DIVIDER];
        }
    }

    // 마지막 위치에서의 총 경우의 수를 반환합니다.
    return (dp[n - 1][0] + dp[n - 1][1]) % DIVIDER;
}