백준/1562번/계단 수/골드1

Problem Link: https://www.acmicpc.net/problem/1562

문제 설명

Site: Baekjoon
Number: 1562
Category: Dynamic Programming / Bit Masking
Rank: Gold 1

주어진 N만큼의 길이를 가진 숫자에 0 ~ 9 모든 숫자를 포함한 계단 수를 찾는 문제입니다.

문제 풀이

3차원 DP 배열을 통해 해결합니다.

dp[i][j][k]에서 i는 길이를 의미하며, j는 계단 수의 마지막 숫자, k는 비트 마스킹을 통해 0 ~ 9 중에 포함하고 있는 숫자를 의미합니다.

처음 존재하는 계단 수는 1 부터 9이므로 이를 모두 초깃값으로 넣고 다음과 같은 점화식을 진행합니다

j = 0인 경우 dp[i][j][k | 1 « j] += dp[i][j+1][k];

j = 9인 경우 dp[i][j][k | 1 « j] += dp[i][j-1][k];

그 외의 경우 dp[i][j][k | 1 « j] += (dp[i][j-1][k] + dp[i][j+1][k]);

모든 연산을 완료한 후 마지막에 k가 1023인 값, 즉 0 ~ 9의 모든 숫자를 포함하는 계단 수만 더하여 출력하면 정답이 나옵니다.

#include <iostream>

using namespace std;

long long dp[101][10][1024];

#define MOD 1000000000

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N;
    cin >> N;

    for(int i = 1; i < 10; i++)
    {
        dp[1][i][1 << i] = 1;
    }

    for(int i = 2; i <= N; i++)
    {
	    for(int j = 0; j < 10; j++)
	    {
            for (int k = 1; k < 1024; k++)
            {
                if (j == 0)
                    dp[i][j][k | (1 << j)] += dp[i - 1][j + 1][k] % MOD;
                else if (j == 9)
                    dp[i][j][k | (1 << j)] += dp[i - 1][j - 1][k] % MOD;
                else
                {
                    dp[i][j][k | (1 << j)] += (dp[i - 1][j - 1][k] + dp[i - 1][j + 1][k] ) % MOD;
                }
            }
	    }
    }

    long long ans = 0;
    for(int i = 0; i < 10; i++)
    {
        ans += dp[N][i][1023] % MOD;
    }

    cout << ans % MOD;

    return 0;
}