[BOJ] 백준 10844 쉬운 계단 수 / 동적 계획법(Dynamic-Programming)

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

 

💣 문제 이해

 

 

1. 45656 과 같이 모든 자리 수가 인접한 자리 수와 1 차이날 때, 그 수를 계단 수 라고 한다.

2. 입력으로 1~100 사이의 자연수 N 이 주어진다.

3. N 자리 자연수 중 계단 수가 총 몇 개인지 찾아 출력하면 된다.

 

동적 계획법(Dynamic Programming) 방식을 사용했다.

 

 

 

 

💭 풀이 과정

 

 

N = 1 인 경우, 1, 2, 3, 4, 5, 6, 7, 8, 9 가 가능하다.

 

문제에 제시된 조건에 따라 0은 불가하다.

 

N = 2 인 경우, 10, 12, 21, 23, 32, 34, .... 98 가 가능하다.

 

1 ~ 9 사이 수를 십의 자리로 하여 일의 자리는 -1 한 수 또는 +1 한 수라는 것을 알 수 있다.

 

 

점화식으로 정리하자면 다음과 같다.

 

 

dp[i][j] = dp[i+1][j-1] + dp[i+1][j+1]

 

i 는 자리수 N 을 뜻하는 dp 배열의 행이고 j 는 그 수의 가장 우측에 위치한 수 1~9 이다.

 

그러나, i 가 0 인 경우는 dp[i+1][j+1] 만 고려하며 i 가 9 인 경우는 dp[i+1][j-1] 만 고려한다.

0 인 경우, -1 은 존재하지 않으므로 10 만 가능하기 때문이고

9 인 경우, 그 이상은 존재하지 않으므로 89 만 가능하기 때문이다.

 

 

 

 

작성 언어: C++

 

#include <cstdio>   // c 표준입출력
#include <algorithm>  // std::fill_n
#define mod 1000000000

int dp[110][10] = {0, };

int sumOfStairs(int index){
    int sum = 0;
    
    for (int i = 2; i <= index; ++i) {
        for (int j = 0; j <= 9; ++j) {
            if (j == 0){
                dp[i][j] = dp[i-1][j+1];
            }else if (j == 9){
                dp[i][j] = dp[i-1][j-1];
            }else{
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % mod;
            }
        }
    }
    
    // 입력으로 받은 N 자리 계단수의 총합 구하기
    for (int i = 1; i < 10; ++i) {
        sum = (sum + dp[index][i]) % mod;
    }
    
    return sum;
}

int main(){
    int nNumber;
    scanf("%d", &nNumber);
    
    // 한자리 숫자를 뜻하는 1번 행의 모든 원소를 1로 초기화
    std::fill_n(dp[0]+10, 10, 1);
    
    printf("%d\n", sumOfStairs(nNumber));
    
    return 0;
}

 

 

 

 

🏆 배운 점

 

 

DP 문제 풀이를 하면서 특정 값으로 나눈 나머지를 출력하라는 문제가 많이 보이기 시작한다.

 

모 블로그를 참고하여 긁어온 식이다. (A + B) % M = (A % M + B % M) % M

 

마지막에 특정 값의 합을 나눈 나머지를 출력해야한다면, 계산 과정 도중에 나누어도 된다는 뜻이다.

 

값이 너무 커서 오버플로우가 발생할 것 같다면, 그때그때 나누어주고 다 더한 값을 최종적으로 나눈 나머지를 출력해도 된다는 것이다.