프로그래밍/알고리즘 풀이
[node.js] 쉬운 계단 수 ( 백준 10844번 )
카카수(kakasoo)
2021. 3. 25. 16:41
반응형
node.js로 푼 사람이 별로 없다는 게 참 슬픈 일이다. 자바스크립트로도 문제를 풀 수 있는데...
이 문제에서 주의할 것은 다음과 같다. ( 이 문제를 굳이 node.js로 검색했다면야... )
- BigInt를 사용할 것.
- Cpp에서만 문제가 될 줄 알고 자만했는데, BigInt 때문에 틀린 것이었다.
- mod를 잊지 말 것. 나누라고 문제에 분명히 나와 있다.
- 혹시나 map 함수나 fill 등의 Array의 프로토타입 함수로 배열을 반환했다면, 모든 인덱스의 배열이 같은 배열을 가리키게 된다.
- 이 부분은 자바스크립트의 특성이므로 기억해두자.
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
rl.on("line", (line) => {
main(Number(line));
rl.close();
}).on("close", () => {
process.exit();
});
const mod = BigInt(1000000000);
/**
*
* @param {number} line
*/
const main = (line) => {
const DP = new Array(line + 1);
for (let i = 0; i <= line + 1; i++) {
DP[i] = [];
}
for (let i = 0; i < 10; i++) {
if (i === 0) {
DP[1][0] = BigInt(0);
} else {
DP[1][i] = BigInt(1);
}
}
for (let i = 2; i <= line; i++) {
for (let j = 0; j < 10; j++) {
DP[i][j] = BigInt(0);
if (j - 1 >= 0) DP[i][j] += DP[i - 1][j - 1];
if (j + 1 <= 9) DP[i][j] += DP[i - 1][j + 1];
DP[i][j] = BigInt(DP[i][j]) % mod;
}
}
const sum = DP[line].reduce((acc, cur) => acc + cur);
console.log(String(sum % mod));
};
조금 어려운 문제였다.
DP를 앞에서부터 하거나 뒤에서부터 하거나 둘 중 하나만 생각하면 될 줄 알았는데,
알고보니 일차원적인 문제에서도 2중 for문이 나올 수 있었다.
조건을 if문이 아닌, 변수 ( 인덱스 )로 생각하는 훈련도 필요할 거 같다.
반응형