P.10844 쉬운 계단 수

castlehi·2022년 3월 26일

목록 보기

48/67

10844 쉬운 계단 수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	99877	31125	22321	29.248%

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1

1

예제 출력 1

9

예제 입력 2

2

예제 출력 2

17

코드

import java.io.*;

public class P_10844 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        long[][] dp = new long[101][10];
        for (int i = 1; i < 10; i++) dp[1][i] = 1;

        for (int i = 2; i < 101; i++) {
            for (int j = 0; j < 10; j++) {
                if (j == 0) dp[i][j] = (dp[i - 1][j + 1]) % 1000000000;
                else if (j == 9) dp[i][j] = (dp[i - 1][j - 1]) % 1000000000;
                else dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
            }
        }

        long sum = 0;
        for (long num : dp[n]) sum += num;
        bw.write(Long.toString(sum % 1000000000));
        bw.flush();
    }
}

코드 설명

이차원배열을 선언해서 dp로 풀었다.
dp[i][j]에서 i는 i자리 계단수를 나타내고, j는 계단수들 중 j로 끝나는 수들의 개수를 저장했다.

n이 1일 때는 1, 2, 3, 4, 5, 6, 7, 8, 9밖에 없으므로 dp[1][1~9]를 모두 1로 초기화해준다.
dp[2]부터는 dp[n - 1]을 이용해야하는데 dp[n][j]의 연속성을 dp[n - 1][j]가 가지고 있기 때문이다.

예시로 dp[3][2]는 212, 432, 232 세 가지인데 2의 바로 앞 숫자로 들어올 수 있는 수는 $2 - 1 = 1$ 이거나 $2 + 1 = 3$ 이다.

우리가 구하려고 하는 것은 세 자리수이기 때문에 1로 끝나는 두 자리 계단수나 3으로 끝나는 두 자리 계단수의 정보를 가져와서 붙이면 된다.
그렇기 때문에 dp[2][1]과 dp[2][3]을 가져와서 더하면 dp[3][2]를 구할 수 있게 된다.

$dp[n][i] = dp[n - 1][i - 1] + dp[n - 1][i + 1]$

그런데 0이나 9로 끝나는 계단수들은 특수성을 가지고 있어서 따로 처리해줘야한다.
위의 수식을 이용할 경우 0은 -1 인덱스, 9는 10 인덱스와 같은 없는 인덱스를 참조해버리기 때문에 0은 $dp[n - 1][i + 1]$ 만 계산을 하고 9는 $dp[n - 1][i - 1]$ 만 계산을 할 수 있도록 해야한다.