[백준][BOJ][C++][JAVA][10844번] 쉬운 계단 수

문제

45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

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

출력

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

코드(C++)

#include<iostream>
using namespace std;
 
int N;
int C;
long long ans;
int dp[101][11];
 
//void check(int c, int n) {
//    bool exit = false;
//    int x = c;
//    int s = c % 10;
//    c /= 10;
//    for (int i = 0; i < n - 1; i++) {
//        int e;
//        e = c % 10;
//        c /= 10;
//        if (s - e == 1) {
//            s = e;
//        }
//        else {
//            exit = true;
//            break;
//        }
//
//    }
//    if (!exit) {
//        //cout << "합격 : " << x << endl;
//        ans++;
//    }
//}
 
long long check(int n) {
    dp[1][0] = 0;
    for (int i = 1; i < 10; i++)
        dp[1][i] = 1;
    for (int i = 2; i < N + 1; 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;
        }
    }
    ans = 0;
    for (int i = 0; i < 10; i++)
        ans += dp[N][i];
 
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N;
    //if (N == 1)
    //    cout << "9";
    //else {
    //    C = 1;
    //    for (int i = 0; i < N; i++)
    //        C *= 10;
    //    for (int i = 10; i < C; i++)
    //        check(i,N);
    //    cout << (ans + 9) % 1000000000;
    //}
    cout << check(N) % 1000000000;
}

코드(JAVA)

import java.util.Scanner;
 
public class Main {
    static long[][] dp;
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        solve(N);
    }
 
    public static final void solve(int n){
        long[][] dp = new long[101][11];
        dp[1][0]=0;
        for(int i =1;i<10;i++)
            dp[1][i]=1;
        
        for (int i = 2; i < n+1; 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 ans =0;
        for(int i=0;i<10;i++)
            ans += dp[n][i];
        System.out.println(ans%1000000000);
        
    }
}
 

 

해설

*c++로 먼저 푼다음 그 식을 java로 옮겨 적었습니다.

처음에는 dp를 안쓰고 그냥 풀었더니 시간초과가 발생하였습니다.

그리하여 dp를 사용해야 한다는 것을 알고 dp를 사용하여 풀이하였습니다.

N번째 자리수의 마지막 자리수에 따른 갯수를 저장하였습니다.

그리고 고려해 주어야 할부분은 마지막 수가 0이거나 9일경우 0이면 맨 뒷자리 수가 1인경우만 가능하고 9일경우는 8만 가능하고 나머지는 예를들어 3인경우 맨뒷자리가 2인수와 4인수가 가능하여 아래와 같은 수식을 사용하여주었습니다.

            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;

와 같은 점화식을 사용하였습니다.

 

위의 설명이 부족할수도 있다고 생각하여 아래 예시를 들겠습니다.

1~9인경우는 모두 계단 수로 dp에 1씩 저장하였고

10~99에서 뒷자리가 0인 10은 11만 가능하고 12는 11과 13이 가능하고 9는 18만 가능하기 때문에 위의 식으로 풀이가 가능합니다.