[JavaScript] 백준 14852 : 타일 채우기 3

level : gold 4
문제 링크 : 타일 채우기 3

14852번: 타일 채우기 3

 
My Solution

const input = require("fs").readFileSync("/dev/stdin").toString().trim();
const N = Number(input);

/**
 * 
 * @param {number} n
 * @returns {number}
 */
function solution(n){
    if(n === 1)
        return 2;
    else if(n === 2)
        return 7;
    let dp = new Array(n+1).fill(0n);
    const max = 1000000007n;
    dp[1] = 2n;
    dp[2] = 7n;
    dp[3] = 22n;
    for(let i = 4; i <= n; i++) {
        dp[i] = ((max + 3n * dp[i - 1]) - dp[i - 3] + dp[i - 2])%max;
	}
	return Number(dp[n]%max);
}

console.log(solution(N));

풀이방법
 
위 문제는 DP문제이며 점화식으로 접근해야합니다.
문제의 예제로 1,2,3째 항을 알려주었습니다.
먼저 n이 1인 경우는 2개이며 n이 2인 경우는 7개, n이 3인 경우는 22개 입니다.
n이 1이나 2인 경우는 찾기가 매우 쉬울 것이나 3이상은 다른 모양이 생깁니다. 따라서 수를 보고 처음에는 규칙성이 잘 안 보입니다.(보인다면 당신은 천재 혹은 그 이상... 저는 안보였습니다.) 그래서 점화식을 세우기가 어려웠습니다.
그리하여 차근차근 그림을 그리며 점화식을 세웠습니다.(설명은 좀 어려운데 그림 보세요. 블로그)

점화식

시그마가 나오길래 코드짜기가 어렵겠다고 생각을 하였습니다. 그리하여 시그마를 없애고 싶다는 생각이 들었고 이를 점화식 전개하였습니다.

점화식 전개

그리하여 코드로 짜기 쉬운 점화식을 만들었습니다. 일반항을 만들면 좋았겠지만 저의 한계로 잘은...ㅎ
마지막 줄에 있는 0을 굳이 1로 안 두고 n을 4부터 주어도 성립합니다! 
그리하여 dp를 이용하여 풀면 편하게 풀 수 있습니다. 하지만 여기서 허점은 계속 1000000007로 나눈 나머지을 저장하다 보니 dp에 음수가 발생할 수 있습니다. 그리하여 점화식 계산할 때, 1000000007를 더해주고 계산후에 1000000007로 나눈 나머지를 dp에 저장하면 됩니다.
 
느낀점
처음 문제를 접한 곳은 나동빈님의 Dynamic Programming설명에서였습니다.
처음에는 어렵다는 느낌만 받았고 2차원 배열로 푸는 풀이에 대하여 의문이 들며 어떠한 점화식이 나와야 했을까라는 생각을 했습니다. 결국 2차원 배열에 쓰인 점화식을 이해하지 못하여 다른 방법으로 풀었습니다.
또한 n보다 큰 index를 참조하는 경우가 생겨 99%에서 계속 TypeError가 발생하여 고생을 했습니다.