[알고리즘 문제 풀기] 계단 수(1562)

1. 문제 풀이 아이디어

• 비트 마스킹과 다이나믹 프로그래밍을 활용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int n = int.Parse(sr.ReadLine());
    long[,,] dp = new long[n + 1, 10, 1024];
    for (int i = 1; i < 10; i++)
    {
        dp[1, i, 1 << i] = 1;
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            for (int k = 0; k < 1024; k++)
            {
                if (dp[i, j, k] == 0) continue;
                dp[i, j, k] %= 1000000000;
                if (j != 0)
                {
                    dp[i + 1, j - 1, k | (1 << (j - 1))] += dp[i, j, k];
                }
                if (j != 9)
                {
                    dp[i + 1, j + 1, k | (1 << (j + 1))] += dp[i, j, k];
                }
            }
        }
    }
    long result = 0;
    for (int i = 0; i < 10; i++)
    {
        result += dp[n, i, 1023];
        result %= 1000000000;
    }
    sw.WriteLine(result);
}

3. 정리

• dp[자리수][마지막숫자][사용된숫자비트] 배열로 상태를 저장한다.

• 자리 수가 1일 때 1~9까지 초기화하고, 비트마스크로 해당 숫자를 사용한 것으로 처리한다.
dp[1, i, 1 << i] = 1

• i자리에 j숫자를 마지막으로 했을 때, 양옆 숫자로만 이동 가능한 계단 수의 규칙에 따라
j-1과 j+1로 다음 자리에 갈 수 있도록 상태를 전이시킨다.

• k는 사용한 숫자를 비트마스크로 저장하므로 k | (1 << 다음숫자)로 다음 상태를 갱신한다.

• 마지막 자리 수에서 비트마스크가 1023 (0~9를 모두 사용한 상태)인 경우만 결과에 더한다.

• 최종 결과는 result %= 1000000000을 통해 1,000,000,000으로 나눈 나머지를 출력한다.