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

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

프로그래머스

 

dp 문제이다.

자세한 것은 주석에 적어 놓았다.

(그래도 짧게 설명하자면,

삼각형을 기준으로 이전 삼각형의 오른쪽 아래 마름모가 있는지 없는지 분기처리 해서 풀었다.)

그리고 코드가 짧아보이는 것은 먼저 분기처리를 한 뒤에 하나로 합쳤다.

 

추가로 공간복잡도를 더 줄인다면

이전 오른쪽 아래 마름모 있는 개수, 이전 오른쪽 아래 마름모 없는 개수

두 개의 변수를 사용하면 된다.

 

참고로 10007로 항상 나눠 줘야 한다. (잘 못하면 오버플로 일어날 수 있다.)

 

/*
설계
dp
점화식
상태는 윗변을 기준 i
삼각형 + 왼쪽 마름모 + 가운데 마름모 -> 0, 오른쪽 마름모 -> 1
=> 윗변 i, 아랫변 i - 1, i + 1 기준
1) i 위에 삼각형이 있는 경우
 (1) i - 1 이 오른쪽 아래 마름모인 경우
 모두 삼각형, 가운데 마름모, 오른쪽 아래 마름모
 (2) 나머지
 모두 삼각형, 왼쪽 + 가운데 + 오른쪽 마름모
2) i 위에 삼각형이 없는 경우
 (1) i - 1 이 오른쪽 아래 마름모인 경우
 모두 삼각형, 오른쪽 아래 마름모
 (2) 나머지
 모두 삼각형, 왼쪽 + 오른쪽 마름모
 
=> 기준 이전 삼각형에 오른쪽 마름모를 사용했는지 안했는지 -> 2차원.
*/

function solution(n, tops) {
    const mod = 10007;
    // 0-index
    const dp = Array.from({length : n}, () => Array(2).fill(0));
    
    // 삼각형 + 왼쪽, (가운데) 마름모
    dp[0][0] = 2 + tops[0];
    
    // 오른쪽 마름모
    dp[0][1] = 1;
    
    for (let i = 1; i < n; i++) {
        // 하나로 합치기 위해서 상수 선언
        const top = tops[i];
        
        dp[i][0] = (dp[i-1][0] * (2 + top) + dp[i-1][1] * (1 + top)) % mod;
        dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % mod
    }
    
    return (dp[n-1][0] + dp[n-1][1]) % mod;
}