문제 링크

성능 요약

메모리: 14196 KB, 시간: 100 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 1월 28일 03:05:30

문제 설명

45656이란 수를 보자.

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

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

입력

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

출력

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

풀이

느낀점

• 비교적 쉽고 간단했다.

설계 : 5분

• 1~9의 수부터 각각 시작해서 이전 숫자가 자신의 앞뒤 숫자인 경우를 더해간다.
• dp 테이블을 모두 채우면 n-1번째 열의 모든 값을 더해 계단 수의 개수를 구한다.

코드(Java)

• 구현 시간: 10분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 쉬운 계단 수_10844
 * Date: 2025.01.28
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
        int[][] dp = new int[10][n];
        for (int i = 1; i < 10; i++) dp[i][0] = 1;

        for (int c = 1; c < n; c++) {
            dp[0][c] = dp[1][c-1] % 1_000_000_000;
            dp[9][c] = dp[8][c-1] % 1_000_000_000;
            for (int r = 1; r < 9; r++) {
                dp[r][c] = (dp[r-1][c-1] + dp[r+1][c-1]) % 1_000_000_000;
            }
        }

        int answer = 0;
        for (int i = 0; i < 10; i++) answer = (answer + dp[i][n-1]) % 1_000_000_000;

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