[백준] 10844번 : 쉬운 계단 수

문제

 

---

풀이

 

n자리의 자연수가 있다고 하자. 우리는 왼쪽부터 오른쪽으로 값을 채워나가고 있고 i번째 자리의 값을 채우려 한다.

i번째가 첫번째 자리, 그니까 가장 왼쪽에 위치한 자리만 아니라면 0~9까지 모든 수가 들어올 수 있다.

 

i번째 자리에 0이 들어간다면 i-1번째 자리의 수는 1일 것이다.

i번째 자리에 9가 들어간다면 i-1번째 자리의 수는 8일 것이다.

i번째 자리에 k(1<k<9)가 들어간다면 i-1번째 자리의 수는 k-1이거나 k+1일 것이다.

---

소스코드

 

#include <iostream>
using namespace std;
#define DIVISOR 1000000000

int dp[101][10]; //n번째의 0~9의 개수를 저장함

int easy_stair(int num) { //뭐 더할 일 있을 때마다 계속 나눠줌
    int result = 0;
    for (int i = 0; i < 10; i++) { //시작점 초기화
        if (i == 0)
            dp[1][i] = 0;
        else
            dp[1][i] = 1;
    }
    for (int i = 2; i <= num; i++) {
        for (int j = 0; j < 10; j++) {
            if (j == 0) //0인 경우는 1에서 건너오는 것
                dp[i][j] = dp[i - 1][j + 1] % DIVISOR;
            else if (j == 9) //9인 경우는 8에서 건너오는 것
                dp[i][j] = dp[i - 1][j - 1] % DIVISOR;
            else //나머지는 이전, 이후 더해줌. ex) 3이면 이전 상황의 2와 4의 개수를 합쳐줌
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % DIVISOR;
        }
    }
    for (int i = 0; i < 10; i++) {
        result += dp[num][i];
        result %= DIVISOR; //더하는 도중에도 계속 나눠줘야 함
    }
    return result;
}

int main() {
    int N;

    cin >> N;
    cout << easy_stair(N) << '\n';
}

전체 소스코드다.

 

int dp[101][10]; //n번째의 0~9의 개수를 저장함

n자리 수가 있을때 i번째 자리의 수가 j(0~9)인 경우의 수를 담는 2차원 배열이다.

dp[3][8]은 n자리 수의 3번째 자리가 8인 경우의 수를 저장한 것이다.

 

    for (int i = 0; i < 10; i++) { //시작점 초기화
        if (i == 0)
            dp[1][i] = 0;
        else
            dp[1][i] = 1;
    }

위에서 말했지만 가장 왼쪽에 위치한 수에 0이 들어갈 순 없을 것이다.

그렇기 때문에 dp[1][0]에는 0을 넣어주고 dp[1][1]~dp[1][9]에는 1을 넣어주며 초기화 한다.

 

    for (int i = 2; i <= num; i++) {
        for (int j = 0; j < 10; j++) {
            if (j == 0) //0인 경우는 1에서 건너오는 것
                dp[i][j] = dp[i - 1][j + 1] % DIVISOR;
            else if (j == 9) //9인 경우는 8에서 건너오는 것
                dp[i][j] = dp[i - 1][j - 1] % DIVISOR;
            else //나머지는 이전, 이후 더해줌. ex) 3이면 이전 상황의 2와 4의 개수를 합쳐줌
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % DIVISOR;
        }
    }

앞서 말한대로 특정 자리에 0이 들어가는 경우, 9가 들어가는 경우, 나머지 수가 들어가는 경우로 나누어 계산을 한다.

 

    for (int i = 0; i < 10; i++) {
        result += dp[num][i];
        result %= DIVISOR; //더하는 도중에도 계속 나눠줘야 함
    }

당연히 마지막자리에 0~9가 들어가는 모든 경우를 더해야 우리가 구하는 답이 나올 것이다.