[JavaScript/DP] 백준 골드 5 : 2410 - 2의 멱수의 합

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

2410번: 2의 멱수의 합

---

📌 작성한 코드 

// 2410
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim();

const N = Number(input);

const dp = Array(N + 1).fill(0);
dp[1] = 1;

for (let i = 2; i <= N; i++) {
    if (i % 2 === 0) {
        dp[i] = (dp[i - 1] + dp[i / 2]) % 1_000_000_000;
    } else {
        dp[i] = dp[i - 1];
    }
}

console.log(dp[N]);

 

📌 설명 

- i가 홀수인 경우 : dp[i]는 dp[i-1]에서 1을 더하는 경우의 수 밖에 없으므로 dp[i] = dp[i-1]

- i가 짝수인 경우 : dp[i-1]에다가 1을 더하는 경우의 수와 dp[i/2]에 2를 곱하는 경우의 수가 존재하므로 dp[i] = dp[i-1] + dp[i/2] 

 

✅ 성공

헤헤 이문제로 골드1됨