2021. 7. 9. 12:53ㆍFront-end/알고리즘
문제를 풀기 위한 아이디어
다이나믹 프로그래밍 문제는 언제나 점화식을 세우는 것이 중요하다.
이번 문제는 dp에서 2차원 배열을 이용해서 저장하는 것을 배울 수 있었던 문제였다.
우선 0으로 시작하는 수는 없다고 했기 때문에,
n=1인 경우 1,2,3,4,5,6,7,8,9 = 9가지 경우가 나온다.
n=2인 경우를 생각해보자. (10,11) (21,23) .... (98)로 다 합치면 17가지 경우가 나온다.
즉 앞의 수가 0이면 뒤에 올 수 있는 수는 1밖에 존재하지 않는다.
만약 앞의 수가 1부터 8이라면 각각 두개씩 존재할 수 있다.
만약 앞의 수가 9라면 뒤에 올 수 있는 수는 8밖에 존재하지 않는다. 이를 염두해두어야 한다.
dp[n][i]를 n자리수 이면서 i로 끝나는 경우라고 한다면,
우선 n=1인 경우는 dp[1] = [0,1,1,1,1,1,1,1,1,1]; 라고 저장해놓는다.
n=2인 경우는 dp[2] = [1,1,2,2,2,2,2,2,2,1];가 된다.
- dp[2][0] = 자리수가 2이면서 0으로 끝나는 수는 10밖에 존재하지 않으므로 1,
- dp[2][1] = 자리수가 2이면서 1로 끝나는 수는 21 밖에 존재하지 않으므로 1,
- dp[2][2] = 자리수가 2이면서 2로 끝나는 수는 12, 32로 2개가 존재하므로 2,
...
- dp[2][9] = 자리수가 2이면서 9로 끝나는 수는 89 밖에 존재하지 않으므로 1)
n=3인 경우부터는 어떨까?
- dp[3][0] = 자리수가 3이면서 0으로 끝나는 수이다. 0으로 끝나기 때문에 바로 직전의 수는 1밖에 올 수 없다. 즉 dp[2][1]의 개수(자리수가 2이면서 1로 끝나는 수의 개수)가 된다.
- dp[3][1] = 자리수가 3이면서 1로 끝나는 수 이다. 1로 끝나기 때문에 바로 직전의 수는 0과 2가 올 수 있다. 즉 dp[2][0] + dp[2][2]가 된다. (자리수가 2이면서 0으로 끝나는 수 + 자리수가 2이면서 2로 끝나는 수)
...
- dp[3][9] = 자리수가 3이면서 9로 끝나는 수 이다. 9로 끝나기 때문에 바로 직전의 수는 8밖에 올 수 없다. 즉 dp[2][8] (자리수가 2이면서 8로 끝나는 수) 이다.
즉 점화식을 세워본다면 n=3부터는
1) i = 0인 경우
dp[n][i] = dp[n-1][i+1]
2) i = 1부터 i = 8까지 인 경우
dp[n][i] = dp[n-1][i-1] + dp[n-1][i+1]
3) i = 9인 경우
dp[n][i] = dp[n-1][i-1]
위와 같은 식이 성립한다.
문제에서 10억으로 나눈 값을 출력하라고 했으므로 저장할 때에도 10억으로 나눈 나머지를 저장하고,
출력할 때에도 10억으로 나눈 나머지를 출력한다.
내가 작성한 코드 (자바스크립트)
let fs = require("fs");
const number = Number(fs.readFileSync("예제.txt").toString());
// dp[n][i] = n자리 수이면서 i로 끝나는 수
const dp = Array.from(new Array(number + 1), () => new Array(10));
dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1];
dp[2] = [1, 1, 2, 2, 2, 2, 2, 2, 2, 1];
for (let n = 3; n <= number; n++) {
for (let i = 0; i < 10; i++) {
if (i === 0) {
dp[n][i] = dp[n - 1][i + 1] % 1000000000;
} else if (i >= 1 && i <= 8) {
dp[n][i] = (dp[n - 1][i - 1] + dp[n - 1][i + 1]) % 1000000000;
} else {
dp[n][i] = dp[n - 1][i - 1] % 1000000000;
}
}
}
let sum = 0;
for (let j = 0; j < 10; j++) {
sum += dp[number][j];
}
console.log(sum % 1000000000);