문제 출처

단계별로 풀어보기 > 동적 계획법1 > 쉬운 계단 수
https://www.acmicpc.net/problem/10844

문제 설명

인접한 모든 자리의 차이가 1인 수를 계단 수라고 할 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하라.
단, 1,000,000,000으로 나눈 나머지를 출력한다.

접근 방법

자리수가 0,9일 때 제외하고, 나머지의 경우는 이전 길이(N-1)에서 digit-1 or digit+1 에서 각각 +1, -1 하게 되면 digit이 되므로, 이전 경우를 더한다.
단, 자리수가 0인 경우는 digit -1을 하면 -1이 되므로 +1만 적용하고, 자리수가 9인 경우에는 digit+1 하면 10이 되므로 -1만 적용한다.
그렇게 적용된 dp[N]의 값들을 모두 더해서 mod로 나누면 결과가 나온다.

import java.io.*;

public class 쉬운_계단_수 {

    final static long mod = 1000000000;

    public static long dp[][];

    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());

        dp = new long[N+1][10];

        for(int i = 1; i < 10; i++){
            dp[1][i] = 1;
        }

        for(int n = 2; n <= N; n++){
            for(int digit = 0; digit < 10; digit++){
                if(digit > 0) dp[n][digit] += dp[n-1][digit-1];
                if(digit < 9) dp[n][digit] += dp[n-1][digit+1];
                dp[n][digit] %= mod;
            }
        }

        long result = 0;

        for(int i = 0; i < 10; i++){
            result = (result + dp[N][i]) % mod;
        }

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

N의 경우를 차례로 나열하다 보면,
dp[n][digit] = dp[n-1][digit-1] + dp[n-1][digit+1] 이란 점화식이 세워지게 된다.
이를 통해서 문제를 풀 수 있다.

해당 코드의 시간 복잡도는 O(N)이 된다.

문제푼 흔적