문제
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
예제 입력 1
1
Plain Text
복사
예제 출력 1
9
Plain Text
복사
예제 입력 2
2
Plain Text
복사
예제 출력 2
17
Plain Text
복사
My solution
N인 계단 수가 총 몇 개 있는지
1 ≤ N ≤ 100
1,000,000,000으로 나눈 나머지를 출력
필요한 조건은 두가지
1.
자릿수 N
2.
앞에 들어온 숫자
따라서 DP는 이차원 배열로
행은 자릿수 1 ~ N이 들어오고
열은 앞에 올 수 있는 숫자인 0 ~ 9가 들어온다.
자릿수가 1일 때는 어떤 값이 들어올지 미리 알 수 있다. 0 ~ 9가 모두 하나씩 들어오면 9가지다.
for (let i = 1; i <= 9; i++) {
DP[1][i] = 1;
}
JavaScript
복사
i행 j열은 자릿수가 i개일 때 어떤 j열에 대해 앞에 올 수 있는 숫자가 j + 1, j - 1이 될 수 있다.
바로 이전 자릿수(행)에서 앞에 올 수 있는 숫자에 해당하는 경우의 수를 모두 가져와서 더하면 현재 자릿수(행)에서 j열의 경우의 수를 구할 수 있다.
매번 이전 자릿수에서의 앞에 올 수 있는 숫자의 영향을 받아 만들어졌기 때문에 자릿수가 3일 때는 자릿수가 2일 때의 경우의 수만 가지고도 구할 수 있다.
ex) 자릿수가 2개일 때 1열에 대해 앞에 올 수 있는 숫자가 1 + 1, 1 - 1
자릿수가 2개일 때 2열에 대해 앞에 올 수 있는 숫자가 2 + 1, 2 - 1 // → 3, 1
자릿수가 2개일 때 3열에 대해 앞에 올 수 있는 숫자가 3 + 1, 3 - 1 // → 4, 2
...
열이 0이면 앞에 올 수 있는 숫자가 1밖에 없고,
열이 9이면 앞에 올 수 있는 숫자가 8밖에 없으므로
이 때는 j + 1, j - 1이 아니라 따로 조건을 나누어 처리한다.
for (let i = 2; i <= N; i++) {
for (let j = 0; j <= 9; j++) {
if (j === 0) {
DP[i][j] = DP[i - 1][1] % 1000000000;
} else if (j === 9) {
DP[i][j] = DP[i - 1][8] % 1000000000;
} else {
// 이전 자릿수의 -1, +1한 숫자인 모든 경우의 수를 더하면 된다.
DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % 1000000000;
}
}
}
JavaScript
복사
값을 할당해주기 전에는 나누는 연산을 해줘서 자료형의 크기를 넘어가지 않도록 한다.
Code
const solution = function (i) {
const N = i.toString().trim() * 1;
// 행 : 1 ~ N 자릿수
// 열 : 0 ~ 9 앞에 올 수 있는 숫자
// 값 : 경우의 수
const DP = Array(N + 1)
.fill(0)
.map(() => Array(10).fill(0));
for (let i = 1; i <= 9; i++) {
DP[1][i] = 1;
}
for (let i = 2; i <= N; i++) {
for (let j = 0; j <= 9; j++) {
if (j === 0) {
DP[i][j] = DP[i - 1][1] % 1000000000;
} else if (j === 9) {
DP[i][j] = DP[i - 1][8] % 1000000000;
} else {
DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % 1000000000;
}
}
}
const result = DP[N].reduce((a, b) => a + b, 0) % 1000000000;
console.log(result);
return result;
};
describe('쉬운계단수', () => {
it('TC1', () => {
expect(solution(`1`)).toStrictEqual(9);
});
it('TC2', () => {
expect(solution(`2`)).toStrictEqual(17);
});
});
JavaScript
복사
