[BOJ 10844] 쉬운계단수 C++ 풀이

문제링크

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

쉬운 계단 수 성공분류

시간 제한 1 초

메모리 제한 256 MB

제출 73324

정답 22248

맞은 사람 15977

비율 28.429%

문제

45656이란 수를 보자.

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

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

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

입력

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

출력

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

풀이

45656처럼 인접한 자리수가 1씩 차이나고, 0으로 시작하는 수는 없습니다.

문제를 조금 더 분석해 보면, 계단수가 되기 위해서는

1뒤에는 0, 9뒤에는 8. 즉, 뒤에 1개의 수만 추가될 수 있습니다.

2~8은 각각 (1,3), (2,4), (3,5), ... (7,9), 즉 뒤에 2개의 수가 추가될 수 있습니다.

 

이러한 특징을 이용하여 DP 배열을 선언해보면,

DP[A][B] = C

DP[이번의 끝 수][수의 길이] = A로 끝나며, 길이가 B인 계단수의 개수C로 선언할 수 있습니다.

 

#include <iostream>

using namespace std;

#define MOD 1000000000

int N;
int dp[9][101];
int ans = 0;

int main()
{
    cin >> N;
    
    // 1, 2, 3, 4, 5, 6, 7, 8, 9는 계단 수, 0으로 끝나는 수는 없음
    for(int i = 1; i <= 9; i++)
        dp[i][1] = 1;

    for(int i = 2; i <= N; i++)
    {
        for(int j =0; j <= 9; j++)
        {
            if(j==0)
            {
		//길이가 i이고 0으로 끝나는 계단 수는 바로 전의 수가 1로 끝나는 것만 가능
                dp[j][i] = dp[1][i-1];
            }
            else if(j== 9)
            {
		//길이가 i이고 9로 끝나는 계단 수는 바로 전의 수가 8로 끝나는 것만 가능    
                dp[j][i] = dp[8][i-1];
            }
            else
            {
		// 2~8로 끝나는 계단수는 (1,3), (2,4), ... (7, 9)이므로
		// j-1, j+1의 개수를 더한것 과 같음
                dp[j][i] += dp[j-1][i-1];
                dp[j][i] += dp[j+1][i-1];
            }
            dp[j][i] %= MOD;
        }
    }

    for(int i = 0; i <= 9; i++)
    {
    	// 0~9까지 끝나며, 길이가 N인 수를 모두 더해서 출력
        ans += dp[i][N];
        ans %= MOD;
    }
    

    cout << ans << '\n';

	return 0;
}

질문과 잘못된 정보 수정 요청은 언제나 환영합니다. 편하게 댓글을 달아주세요.

오늘도 부족한 제 글을 읽어주셔서 감사합니다.