[BOJ] 10844번 | 쉬운 계단 수 (C++)

🔗문제 보러가기

10844번: 쉬운 계단 수

 

🧑🏻‍💻풀이 과정

N자리 숫자에서 일의 자리가 0 ~ 9로 끝나는 계단 수들의 개수를 알아봅시다. 먼저, \( N = 1\)일 때는 다음과 같습니다.

 

[ N = 1 일 때 ]

i = 0	i = 1	i = 2	i = 3	i = 4	i = 5	i = 6	i = 7	i = 8	i = 9
0	1	1	1	1	1	1	1	1	1

 

[ N = 2 일 때 ]

i = 0	i = 1	i = 2	i = 3	i = 4	i = 5	i = 6	i = 7	i = 8	i = 9
1	1	2	2	2	2	2	2	2	1

 

[ N = 3 일 때 ]

i = 0	i = 1	i = 2	i = 3	i = 4	i = 5	i = 6	i = 7	i = 8	i = 9
1	3	3	4	4	4	4	4	3	2

 

 

이 정도까지 진행해보니, 규칙성이 보이기 시작합니다.

N 자리 숫자에서 i 숫자로 끝나는 계단 수의 개수를 저장하는 배열을 dp[N][i]라고 한다면, 규칙성은 다음과 같습니다.

dp[N][0] = dp[N-1][1]
dp[N][i] = dp[N-1][i-1] + dp[N-1][i+1];    (i > 0 and i < 9)
dp[N][9] = dp[N-1][8]

 

즉, 동적 프로그래밍을 이용하여 N = 1일 때의 i값들을 바탕으로 N = 2, N = 3의 값들을 차례대로 알아낼 수 있습니다.

또한, 동적 프로그래밍에 사용할 배열은 \( 2 \times 10 \) 크기만 가진다면, 모든 N에 대한 계단 수 개수를 알아낼 수 있습니다.

 

 

이것이 어떻게 가능할까요? 저는 다음과 같은 방법으로 구현할 수 있었습니다.

먼저, 행을 가리키는 변수를 다음과 같이 2개 선언합니다.

int writeBufferIndex = 0, readBufferIndex = 1;

• writeBufferIndex는 readBufferIndex의 행에서 읽어와 새로 값을 쓰게 되는 행을 의미합니다.
• 위에서 만들었던 점화식에 비유하자면, writeBufferIndex는 N, readBufferIndex는 N - 1에 해당한다고 볼 수 있습니다.
• 한 행에 대하여 모두 연산이 끝났다면, writeBufferIndex와 readBufferIndex가 서로 값을 교환함으로써, 역할을 바꿔서 다시 연산을 이어나가게 됩니다.

 

N이 클수록 2차원 배열의 크기가 커지게 되어 메모리를 많이 쓰게 됩니다. 저는 위 점화식을 도출하는 과정에서 행이 N개까지 필요 없을 것 같다는 생각이 들었고, 그래픽스 렌더링에서 사용되는 더블 버퍼링(Double Buffering) 기법에서 아이디어를 얻어, 위와 같이 알고리즘을 구성하게 되었습니다.

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000000;
const int DIGIT_COUNT = 10;
const int BUFFER_COUNT = 2;

void Swap(int& x, int& y)
{
    int temp = x;
    x = y;
    y = temp;
}

int main()
{
    ios::sync_with_stdio(false);
    cout.tie(NULL); cin.tie(NULL);

    int N;
    cin >> N;

    // 1. 초기화
    vector<vector<int>> dp(BUFFER_COUNT, vector<int>(DIGIT_COUNT));
    int writeBufferIndex = 0, readBufferIndex = 1;
    int sum = 9;

    for (int i = 1; i < DIGIT_COUNT; i++)
        dp[writeBufferIndex][i] = 1;
    // ------------------------------------

    // 2. 로직
    Swap(writeBufferIndex, readBufferIndex);
    for (int i = 1; i < N; i++)
    {
        sum = 0;

        for (int j = 0; j < DIGIT_COUNT; j++)
        {
            if (j == 0 or j == 9)
            {
                int targetIndex = (j == 0) ? j + 1 : j - 1;
                int newValue = dp[readBufferIndex][targetIndex];

                dp[writeBufferIndex][j] = newValue;
                sum = (sum + newValue) % MOD;
                continue;
            }

            dp[writeBufferIndex][j] = (dp[readBufferIndex][j - 1] + dp[readBufferIndex][j + 1]) % MOD;
            sum = (sum + dp[writeBufferIndex][j]) % MOD;
        }

        Swap(writeBufferIndex, readBufferIndex);
    }

    cout << sum;
    return 0;
}