[TIL] 24.07.09 백준 10844번 js

내가 푼 문제 📖

 

내가 작성한 코드 💻

let input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : __dirname+"/input.txt")
  .toString()
  .trim()

let number = +input
let mod = 1000000000
const memo = Array.from({length: 10}, () => 1 )
memo[0] = 0

for(let i=1; i<number; i++){
  const memo_copy = [...memo]
  for(let j=0; j<=9; j++){
    if(j === 0) memo[0] = memo_copy[1] % mod;
    else if(j === 9) memo[9] = memo_copy[8] % mod;
    else memo[j] = (memo_copy[j-1] + memo_copy[j+1]) % mod
  }
}

console.log(memo.reduce((a, c) => (a + c) % mod, 0));

 

어려웠던 점 ❓

1. 점화식 이후 코드 작성까지 연결이 잘 안 된 것

memo[n] = memo[n-1]+1, memo[n-1]-1

 

처음에 세운 점화식이다!! 그러나,, 이후 코딩까지 생각해내지는 못했다. 

// N이 1일 경우 
// 1, 2, 3, 4, 5, 6, 7, 8, 9

// N이 2일 경우
// 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98

 

N이 2일 때 17가지 경우의 수가 나오게 되는데 숫자 0과 9는 +- 1을 하게 될 경우 각각 숫자 1, 숫자 8 이렇게 1가지 경우의 수만 나오게 된다.

 

if(j === 0) memo[0] = memo_copy[1] % mod;
else if(j === 9) memo[9] = memo_copy[8] % mod;

 

그래서 따로 조건문을 추가해 주었다.

 

느낀 점 ❕

1. 조금씩 발전하고 있다는 걸 느낀 하루

점화식을 얼추 비슷하게 세운 것 같은데 아직은 많이 부족하다는 느낌을 받았다.

DP 문제는 점화식을 세우는 게 굉장히 중요하다고 하는데 처음엔 점화식조차 떠오르지도 않았는데 이젠 오랜 고민과 생각 끝에 조금 끄적이는 정도는 할 수 있어서 나름 발전했다고 생각한다.

 

DP 문제를 풀면서 느끼는 거지만 코딩을 하는 것보다 점화식을 세우기 위해 생각과 고민하는 과정에 시간이 더 많이 든다. 처음엔 아무리 생각해도 점화식이 떠오르질 않아 좌절을 많이 했지만 이 또한 겪어보지 못한 문제들이었기 때문이라는 생각이 든다.

더 많은 문제들을 경험하면서 발전할 일만 남았다!!

회고 🧐

다음 주부터는 코딩문제를 아침에 풀어야 되기 때문에 살짝 걱정이 된다.그래서 좀 더 일찍 문제를 푸는 연습을 해야겠다.

---

출처 🏷️

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