백준 문제 풀이 - 쉬운 계단 수 (10844번 문제)
백준 10844번 : 쉬운 계단 수
본문
제한
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
예제 입력 1
1
예제 출력 1
9
예제 입력 2
2
예제 출력 2
17
풀이
어떻게 문제를 풀 수 있을지 '계단 수'를 직접 작성해보면서 규칙을 확인해보자.
먼저 N이 1일 때를 확인해보자.
N이 1이므로 구해야 할 계단 수는 1 자릿수의 수들이다.
1, 2, 3, 4, 5, 6, 7, 8, 9가 이에 속한다.
이제부터 k라는 변수를 두고 이를 증가시켜가며 k번째 자리의 수를 선택, k번째 자리의 수가 i일 때, 몇 개의 계단 수들이 가능한지 확인해보겠다.
여기서 k번째 자리란, 수의 왼쪽부터 시작해서 k번째에 위치한 자리를 말한다.
4354가 주어지고 2번째 자리라면 3을 말하는 것이다.
이번엔 N이 2 일 때를 확인해보자.
N이 2라는 말은 두 자릿수의 숫자를 말한다.
예를 들어 X0 이 계단 수가 되도록 X 값을 구해야 한다고 하자.
X0이 계단 수가 되려면 X는 1이 되어야 한다.
이는 N이 1일 때, 첫 번째 자릿수의 값이 1인 경우의 수와 같다.
이번엔 X1이 계단 수가 되도록 X 값을 구해야 한다고 하자.
X1가 계단 수가 되려면 X는 2가 되어야 한다.
이는 N이 1일 때, 첫 번째 자릿수의 값이 2인 경우의 수와 같다.
이번엔 X2가 계단 수가 되도록 X 값을 구해야 한다고 하자.
X2가 계단 수가 되려면 X는 1 또는 3이 될 수 있다.
이는 N이 1일 때, 첫 번째 자릿수의 값이 1, 3인 경우의 수와 같다.
이번에는 N이 3 일 때를 확인해보자.
N이 3이라는 말은 세 자릿수의 숫자를 말한다.
XX0이 계단 수가 되기 위해서의 가능한 XX의 조합을 구해보자.
우리는 3번째 자리수가 0인 것을 안다.
0의 이전에는 1만 가능하다.
X1이 되는 X를 구해야 한다.
X1은 어떻게 구하는가?
앞서 N이 2일 때 X1의 경우의 수를 이미 구하였다.
XX1가 계단 수가 되기 위한 XX의 조합도 생각해보자.
세 번째 자릿수가 1이기 때문에 XX는 X0, X2가 가능하다.
X0과 X2가 되는 조합은 이미 N이 2일 때 구하였다.
위 내용을 확인해보면 이전 로직 수행 결과를 활용하기 때문에 동적 계획법을 사용할 수 있을 것 같다.
dp 테이블을 2차원 배열로 선언하여 k번째 자릿수의 값이 i일 때, 계단 수를 만들 수 있는 조합의 갯수를 기록하도록 하자.
dp[k][i]에 기록되는 값은 위에서 설명한 대로 k번째 자릿수의 값이 i일 때, 계단 수를 만들 수 있는 조합의 갯수이다.
dp 테이블로 점화식을 도출하면 다음과 같은 점화식을 얻을 수 있다.
i가 0일 때, k-1번째 자리에 올 수 있는 값은 1 뿐이므로, dp[k][i] = dp[k-1][1]i가 9일 때, k-1번째 자리에 올 수 있는 값은 8 뿐이므로, dp[k][i] = dp[k-1][8]- 그 외에
k-1번째 자리에 올 수 있는 값은 i-1, i+1이므로, dp[k][i] = dp[k-1][i-1] + dp[k-1][i+1]
반복을 통해 dp 테이블을 완성하고, dp[N]의 모든 원소들을 더해서 결과로 반환하면 된다.
위 내용을 토대로 작성한 코드는 다음과 같다.
import java.io.*;
import java.util.*;
public class Main {
private static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 1 <= N <= 100, N은 수의 길이
dp = new int[N + 1][10];
for (int i = 1; i < 10; i++) dp[1][i] = 1;
for (int i = 2; i <= N; i++) {
for (int j = 0; j < 10; j++) {
if (j == 0) dp[i][j] = dp[i - 1][1];
else if (j == 9) dp[i][j] = dp[i - 1][8];
else dp[i][j] = mod(dp[i - 1][j - 1] + dp[i - 1][j + 1]);
}
}
System.out.println(Arrays.stream(dp[N]).reduce(0, (left, right) -> mod(left + right)));
}
private static int mod(long num) {
return (int) (num % 1_000_000_000);
}
}