[boj 2193] 이친수

// 이친수

// dp[i][0] = dp[i-1][1]+dp[i-1][0]
// dp[i][1] = dp[i-1][0]

const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = require('fs').readFileSync(filePath).toString().trim().split(/\s/);

const N = input.shift();

const sol = (N) =>{
    const dp = Array.from(Array(91), () => new Array(2).fill(0));
    dp[1][1] = 1;
    dp[2][0] = 1;

    for(let i=3; i<=N; i++){
        dp[i][0] = BigInt(dp[i-1][0]) + BigInt(dp[i-1][1]);
        dp[i][1] = BigInt(dp[i-1][0]);
    }

    console.log((dp[N][0] + dp[N][1]).toString());


}

sol(N);

 

다이나믹 프로그래밍은 너무 어렵따.. 다른 문제들을 다른 분들의 풀이를 보며 이해해보고 처음으로 내 힘으로 풀어봤다.

문제의 규칙을 찾아내 점화식을 작성하는게 핵심인 것 같다.

 

자리수를 i, 끝 자리의 수를 j 라고 했을때 dp[i][0]은 i자리의 0 으로 끝나는 개수, dp[i][1]은 i 자리의 1로 끝나는 개수 

끝자리가 0이면 0과 1이 올수 있고 1이면 0만 올 수 있다.

 

끝자리    다음 끝자리

0     ->     0,1

1     ->      0

 

따라서

dp[i][0] = dp[i-1][1] + dp[i-1][0];

dp[i][1] = dp[i-1][0];

라는 식을 세울 수 있다.

 

값이 자꾸 커지기 때문에 안정적으로 큰 정수값을 담을 수 있는 BigInt로 담아서 arr에 대입하고 출력해주어야한다!