[백준(baekjoon) 10844] 쉬운 계단 수

문제

백준 10844

n(1…100)이 주어질 때, 길이가 n인 계단 수를 구하는 문제

• 계단 수 : 인접한 수의 차이가 1인 수
• 예시 : 12321, 3456, 101
• 주의 : 0으로 시작하는 수는 없다.

해결

계단 수는 끝자리를 기준으로 하기 때문에, *끝의 자리가 0...9인 경우를 각각 따져보면 된다.
N이 100이하이기 때문에, 100 * 10을 해도 1초가 넘지 않으므로 시간초과가 되지 않는다.

N = 1의 경우, 0을 제외한 1...9까지가 가능하다.
이 경우는 무조건 초기화 해준다.

(N > 1)을 만족하는 길이가 N인 계단 수의 규칙은 다음과 같다.

• 끝자리가 0 인 계단 수 : 직전 값이 1일 경우에만 가능
• 끝자리가 9 인 계단 수 : 직전 값이 8일 경우에만 가능
• 끝자리가 1~8 인 계단 수 : 직전 값이 자신 - 1, 자신 + 1인 경우

sum(n)이 길이가 n인 계단 수의 총 개수, dp[n][i] 그 중 i로 끝나는 개수 라고 할 때,
위의 규칙을 활용하여 다음과 같은 식을 세울 수 있다.
sum(n) = sum(n-1) * 2 - (dp[n-1][0] + dp[n-1][9])

0, 9를 제외한 모든 수들은 2개씩 수가 증가하므로 * 2를 우선 해주고
0, 9인 경우는 1개만 증가하므로 그 개수만큼 다시 빼준다.

알고리즘

DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다.

DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자.

구현 java

1. Top-Down 방식

1.import java.util.*;
2.
3.public class Main {
4.    static int[][] dp;
5.
6.    public static void main(String[] args) {
7.        Scanner sc = new Scanner(System.in);
8.        int N = sc.nextInt();
9.
10.        dp = new int[N][10];
11.        getTo(N);
12.
13.        long sum = 0;
14.        long answer = 9;
15.        if (N > 1) {
16.            for (int i = 0; i < 10; i++) sum += dp[N-1][i];
17.            answer = (sum * 2 - dp[N-1][0] - dp[N-1][9]) % 1000000000;
18.        }
19.        System.out.println(answer);
20.    }
21.
22.    static int[] getTo (int n) {
23.        int[] temp = new int[10];
24.        if (n == 1) {
25.            for (int i = 1; i < 10; i++) temp[i] = 1;
26.        }
27.        else {
28.            dp[n-1] = getTo(n-1);
29.            temp[0] = dp[n-1][1];
30.            temp[9] = dp[n-1][8];
31.            for (int i = 1; i < 9; i++)
32.                temp[i] = (dp[n-1][i-1] + dp[n-1][i+1]) % 1000000000;
33.        }
34.        return temp;
35.    }
36.}

2. Bottom-Up 방식

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        int N = sc.nextInt();
7.
8.        long[] count = new long[10];
9.        long sum = 9;
10.        for (int i = 1; i < 10; i++) count[i] = 1;
11.
12.        for (int i = 2; i < N; i++) {
13.            long[] temp = new long[10];
14.            temp[0] = count[1];
15.            temp[9] = count[8];
16.            sum = temp[0] + temp[9];
17.
18.            for (int j = 1; j < 9; j++) {
19.                temp[j] = (count[j-1] + count[j+1]) % 1000000000;
20.                sum += temp[j];
21.            }
22.            count = temp;
23.        }
24.
25.        System.out.println(N == 1 ? sum : (sum * 2 - count[0] - count[9]) % 1000000000);
26.    }
27.}

결과

1. Bottom-Up 방식
2. Top-Down 방식