[ 백준 10844 ] 쉬운 계단 수(C++)

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

 

문제!

---

45656이란 수를 보자.

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

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

 

---

N자리의 계단수의 갯수를 구하는 문제!

 

딱히.... 이해가 어려운 부분은 없었습니다.

 

이번엗도 역시 어느부분을 메모이제이션하여 넘겨줄지를 정해야 하는게 고민인 문제...

 

 

 

시작!

---

저는 현재 상태  1 2 3 4 5 6 7 8 9 에서 뒤에 숫자를 붙여 주는것으로 일단 생각했습니다.

 

 

  int N;
    long long answer = 0;

    cin >> N;

    //1           2          3       4        5        6        7         8       9
    // 12 10     23  21    34  32   45 43    56 54    67 65    78 76    89 87    98

 

 

이렇게 적어보니 끝자리만 생각 해주면 된다고 생각되었고

 

 

 

 

dp에는 길이당 끝자리의 갯수로 나누어 저장해주었습니다.

long long cal[101][11] = {0}; // 길이당 계단수 갯수[끝자리]

 

그러면  n의 자릿수 계산을 할때 ,   

n-1 끝자리가 0인 수는 1로만 연결가능하고

끝자리가 9인 수는 8로만 연결가능하게 계산가능합니다!

 

 

 

 

 

한자리의 초깃값을 설정해주고

for (int i = 1; i < 10; i++) {// 한자리
        cal[1][i] = 1;
    }
    cal[1][0] = 0;

    for (int i = 2; i < N + 1; i++) {// 두자리 이상
        for (int j = 0; j < 10; j++) {// 뒤에붙이기
            if (j == 0) {// 1
                cal[i][j] = cal[i - 1][1];
            }
            else if (j==9) {// 8
                cal[i][j] = cal[i - 1][8];
            }
            else {
                cal[i][j] = (cal[i - 1][j-1]+ cal[i - 1][j + 1])%1000000000;
            }
        }
    }

N이 나올때까지 연산을 하게되면!

 

마지막cal[N][0~9] 까지의 합이 답이 됩니다!

 

 

 

 

동적계획법문제들은 코드는 짧지만 역시 생각을 많이 하게 만드는 문제들인것 같습니다....

 

 

 

 

ALL

#include <iostream>
#include <vector>

using namespace std;

long long cal[101][11] = {0}; // 길이당 계단수 갯수[끝자리]


int main() {
    int N;
    long long answer = 0;

    cin >> N;

    //1           2          3       4        5        6        7         8       9
    // 12 10     23  21    34  32   45 43    56 54    67 65    78 76    89 87    98  

    for (int i = 1; i < 10; i++) {// 한자리
        cal[1][i] = 1;
    }
    cal[1][0] = 0;

    for (int i = 2; i < N + 1; i++) {// 두자리 이상
        for (int j = 0; j < 10; j++) {// 뒤에붙이기
            if (j == 0) {// 1
                cal[i][j] = cal[i - 1][1];
            }
            else if (j==9) {// 8
                cal[i][j] = cal[i - 1][8];
            }
            else {
                cal[i][j] = (cal[i - 1][j-1]+ cal[i - 1][j + 1])%1000000000;
            }
        }
    }

    for (int i = 0; i < 10; i++) {
        answer = (answer + cal[N][i]) % 1000000000;
    }

    cout << answer << endl;

}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!