[Javascript] 3 x n 타일링 (12902)

문제링크

코딩테스트 연습 - 3 x n 타일링

 

접근 방법

2 * n 타일링은 규칙이 눈에 보여서 쉽게 dp를 적용할 수 있었는데..

3 * n 이 되니 규칙이 눈에 보이지 않았다.

그래서 딱 n이 10일때까지만 참고하여 규칙을 생각해봤는데 (3, 11, 41, 153, 571...)

dp[num] = dp[num-1] * 3 + (dp[num-1] - dp[num-2]) 라는 공식을 구할 수 있었다.

그래서 단순히 dp[num] = (dp[num-1] * 3 + (dp[num-1] - dp[num-2])) % 1000000007을 적용해 봤는데
통과하지 못했다.

공식에 - 가 있어서 dp[num] < dp[num-1] 인 경우가 생기기 때문이다.
(dp[num] > 1000000007이고 dp[num-1] < 1000000007 인 경우 dp[num] < dp[num-1]이 됨)

이는 간단하게 dp[num] + 1000000007 적용하여 다음 계산에 사용하면 된다.

dp[num] = tmpVal > 0 ? tmpVal % 1000000007 : tmpVal + 1000000007;​

function solution(n) {
    var answer = 0;
    const dp = Array.from({length : (n/2)+1}, () => 0);
    dp[1] = 3;
    dp[2] = 11;
    
    for(let num = 3; num <= n/2; num++){
        let tmpVal = (dp[num-1] * 3) + (dp[num-1] - dp[num-2]);
        dp[num] = tmpVal > 0 ? tmpVal % 1000000007 : tmpVal + 1000000007;
    }
    
    return dp[n/2];
}