Node.js) 백준 9625번: BABBA

https://www.acmicpc.net/problem/9625

9625번: BABBA

dp[i][a] 는 버튼을 i번 눌렀을 때, A의 개수

dp[i][b] 는 버튼을 i번 눌렀을 때, B의 개수

조건식

dp[i][a] = dp[i-1][b] (i>0);

dp[i][b] = dp[i-1][a] + dp[i-1][b] (i>0);

초기값

dp[0]=[1,0]

 

 

const input = +require('fs').readFileSync('./dev/stdin').toString().trim();
let dp = Array.from(Array(46), () => Array(2).fill(0));
dp[0] = [1, 0];
for (let i = 1; i <= 45; i++) {
	const a = dp[i - 1][0];
	const b = dp[i - 1][1];
	dp[i] = [b, a + b];
}
console.log(dp[input].join(' '));