[백준/C언어] 10844번 - 쉬운 계단 수

백준 웹사이트 "10844번 - 쉬운 계단 수" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

10844번: 쉬운 계단 수

---

소스 코드

#include <stdio.h>

int main(void){
    int N;
    scanf("%d", &N);

    int stair[N+1][10]; //stair[n][i]: 길이가 n, 마지막 자리가 i인 계단수의 개수 
    stair[1][0]=0;
    for(int i=1; i<=9; i++){
        stair[1][i]=1;
    }

    for(int i=2; i<N+1; i++){
        stair[i][0] = stair[i-1][1]%1000000000;
        for(int j=1; j<=8; j++){
            stair[i][j] = (stair[i-1][j-1] + stair[i-1][j+1])%1000000000;
        }
        stair[i][9] = stair[i-1][8]%1000000000;
    }

    int sum=0;
    for(int i=0; i<10; i++){
        sum = (sum + stair[N][i])%1000000000;
    }
    printf("%d\n", sum);
}

---

문제 풀이

  'stair[N+1][10]'은 길이와 마지막 자리에 따른 계단수의 개수를 의미합니다. 구체적으로, 'stair[n][i]'는 길이가 n, 마지막 자리가 i인 계단수의 개수입니다. 길이가 1인 계단수는 1~9까지가 있으므로, stair[1][1] ~ stair[1][9]는 1이 되겠죠? 0으로 시작하는 수는 계단수가 아니므로, stair[1][0]은 0이 됩니다. 이러한 초기값을 이용해 동적 계획법을 시행합니다.

  길이가 i인 계단수의 마지막 자리가 1이기 위해서, 마지막 자리를 제외한 i-1개의 수는 마지막 자리가 0 또는 2인 계단수가 되어야 합니다. 마찬가지로 마지막 자리가 2이기 위해서, 이전 i-1개의 수는 마지막 자리가 1 또는 3인 계단수가 됩니다. 이러한 원리에 의해 다음과 같은 관계식이 생깁니다.

$$ stair[i][j] = stair[i-1][j-1] + stair[i-1][j+1] $$

이는 i가 1 ~ 8일 때 해당되는 관계식입니다. i가 0 또는 9라면, 0 보다 작은 자릿수 또는 9 보다 큰 자릿수가 존재하지 않으므로, 다음과 같은 관계식을 따릅니다.

$$ stair[i][0] = stair[i-1][1] $$

$$ stair[i][9] = stair[i-1][8] $$

  이러한 관계식을 코드로 작성하면, 아래와 같습니다. 이때 '1,000,000,000으로 나눈 나머지'를 출력하는 문제이므로, overflow를 방지하기 위해 배열에 저장하기 전에 1,000,000,000으로 나눈 후 저장합니다.

 

for(int i=2; i<N+1; i++){
    stair[i][0] = stair[i-1][1]%1000000000;
    for(int j=1; j<=8; j++){
        stair[i][j] = (stair[i-1][j-1] + stair[i-1][j+1])%1000000000;
    }
    stair[i][9] = stair[i-1][8]%1000000000;
}

 

  최종적으로 출력해야할 것은 어느 한 자릿수에 대한 계단수의 개수가 아닌, 모든 자릿수에 대한 계단수의 개수입니다. 따라서 stair[N][0] ~ stair[N][9]의 수를 모두 합한 값을 1,000,000,000으로 나눠 출력합니다.

 

int sum=0;
for(int i=0; i<10; i++){
    sum = (sum + stair[N][i])%1000000000;
}
printf("%d\n", sum);