쉬운 계단 수 성공분류

문제

45656이란 수를 보자.

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

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

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

입력

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

출력

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

핵심

마지막자리 수가 1~8이라면 그 뒤에 숫자 두 개씩 올 수 있지만, 0은 그 뒤에 1만, 9는 그 뒤에 8만 올 수 있다.
마지막자리 수 정보를 함께 저장하는 dp 점화식을 만들어보자. (참고로 Dynamic Programming 줄여서 dp임. 동적 계획법 문제 풀 때 쓰는 배열 이름을 주로 dp라고 함. 혹시나 처음 공부하는 사람들이 잘 모를까봐...ㅎㅎ)
숫자가 클 예정이기 때문에 int형 말고 long이나 long long을 사용하자.

코드

#include <iostream>
#include <algorithm>


using namespace std;

long long n, answer;  // 숫자가 크기 때문에 long long 같이 큰 숫자를 넣을 수 있는 자료형을 선택한다. 무심결에 int형으로 했다가 처음에 틀렸다.
long long dp[110][10]; // dp[n][l] : n : 자리 수, l : 마지막 숫자



int main(int argc, char* argv[]) {
	ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    
    for(int i=1;i<=9;i++){
        dp[1][i] = 1;
    }
    
    for(int i=2;i<=n;i++){
        dp[i][0] = dp[i-1][1];
        for(int j=1;j<=8;j++){
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000;  //문제에서 1000000000으로 나눈 나머지를 달라고 했으므로
        }
        dp[i][9] = dp[i-1][8];
    }
    
    for(int i=0;i<=9;i++){
        answer += dp[n][i];
    }
	
    
    cout << answer % 1000000000 << '\n';
    
	return 0;
}

해설

한 시간동안 고민했는데 막상 보니까 간단한 점화식 하나로 끝나서 좀 허탈했다.😂

직접 몇 개의 계단 수를 만들어보자

10,12,21,23,32,34, ...... , 87,89,98,90

마지막 자리가 1~8이라면 뒤에 숫자 두 개가 올 수 있다.

(자기보다 1 큰 숫자, 자기보다 1 작은 숫자가 올 수 있으므로)

이를 고려해서 점화식을 세워보도록 하자.

n : 자리 수, l : 마지막자리 숫자

dp[n][l] = dp[n-1][l-1] + dp[n-1][l+1];

하지만 뒷 자리가 0으로 끝난다면 그 다음 숫자는 1밖에 올 수가 없고, 9로 끝난다면 8밖에 올 수가없다.

그렇기 때문에 l=0, 9일 때의 상황을 나눠주어야 한다.

따라서,

switch(l):
	case 0:
    	dp[n][l] = dp[n-1][1]; //마지막자리 수가 0이라면 그 뒤로 1만 올 수가 있다.
        break;
    case 9:
    	dp[n][l] = dp[n-1][8]; //마지막자리 수가 9이라면 그 뒤로 8만 올 수가 있다.
        break;
    default:
    	dp[n][l] = dp[n-1][1-1] + dp[n-1][l+1];
        break;

요런 느낌으로 접근해주면 좋을 것 같다.

다만, 이중 반복문을 돌려야 하므로, 답안 코드처럼반복문안에 굳이 조건문을 넣을 필요는 없다.