[백준] 1562번 : 계단 수 - C++ / JAVA

백준 1562 : 계단 수

등급 : Gold I

1562번: 계단 수 (acmicpc.net)

1562번: 계단 수

사용 알고리즘 : Bitmasking, Dynamic Programming

사용 자료구조 : -

 

다이나믹 프로그래밍에 비트필드 배열을 추가한 형식의 문제이다.

길이가 5인 수의 경우를 예로 들어보자.

행 부분은 길이, 열 부분은 그 위치에 올 수 있는 숫자이다.

계단 수는 0으로 시작할 수 없으므로 위와 같은 상태가 된다.

두 자리 수의 경우, 0은 1에서만 올 수 있으므로 1.

  → 두 자리 수이며, 두 번째 자리가 0인 계단 수는 10 하나 뿐이다.

  → 마찬가지로 9의 경우도 8에서만 올 수 있다.

중간에 있는 경우, 2를 예로 들면 1과 3에서 올 수 있으므로 1 + 1 = 2.

이와 같은 과정을 거쳐 완성하면 위와 같은 DP 테이블이 완성된다.

여기까지 이해가 되었다면, 이제 어떤 숫자가 등장하였는지 비트필드 차원을 추가시켜주면 된다.

0부터 9까지 모든 숫자가 포함되었는지를 확인할 것이므로 총 2¹⁰개의 비트필드가 필요하다.

위의 예인 45656은 4, 5, 6이 표시된 것이기 때문에 비트로 표현하면 0001110000₂이며, 112가 된다.

이러한 비트 패턴을 위의 DP테이블에 추가할 것이다.

첫 번째 자리의 경우 하나씩만 들어가므로, 수에 맞춰 비트를 Shift해 준 값만큼 필드에 마스킹이 된다.

이후 자리의 경우는 이전 자리에 현재 자리의 수를 OR연산한 것에 이전 자리의 비트를 더해 갯수를 구할 수 있다.

  → 예를 들어 길이가 5인 수이며, 현재 자리에 6이 나오는 경우라고 하고, 4, 5, 6이 마킹된 경우를 보도록 하자.

       나올 수 있는 수는 45656, 45456, 65456이 있겠다. 이때 4565에서 1개, 4545에서 1개, 6545에서 1개가 올 수 있다.

       이때, DP[5][6][0b000111000]에서 2개(4, 5, 6 마킹), DP[5][6][0b000011000]에서 1개(4, 5 마킹)가 올 수 있다.

       즉 (이전 비트 | 현재 숫자 비트)값을 이전 비트들의 합으로 나타낼 수 있다. 

---

  1. 3차원 DP 배열을 생성해준다.

       ( 첫 번째는 길이, 두 번째는 올 수 있는 숫자 (0~9), 세 번째는 올 수 있는 숫자를 마킹할 마스킹 비트 )

  2. 첫 번째 자리의 경우 0에는 올 수 없고, 1~9만 올 수 있으므로 1~9와, 해당하는 비트를 마스킹한 곳에 1을 표시.

      → DP[1][i][1<<i] = 1;

  3. 이후 자리는 위에서 설명한 것과 같이 0과 9의 경우 양 옆에서 하나씩, 나머지는 양쪽에서 받아오는 것으로 구현.

      그리고 비트를 확인하여 이전 비트에 현재 수를 OR 연산한 값의 갯수를 더해준다.

  4. 이후 최대 길이에서 모든 비트가 체크되어 있는 경우를 구한다. 

  ( 문제 조건에 따라, 각 과정에서 모두 %연산을 취해준다. )

---

<hide/>
#include <iostream>

using namespace std;
#define ll long long
#define mod (int)1e9

int dp[101][10][1 << 10] = { 0 };
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    ll ans = 0;
    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 = 0; k < (1 << 10); k++)
            {
                if (j == 0) dp[i][j][k | 1 << j] = (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][j][k | 1 << j] + dp[i - 1][j - 1][k]) % mod;
                else dp[i][j][k | 1 << j] = (dp[i][j][k | 1 << j] + dp[i - 1][j - 1][k] + dp[i - 1][j + 1][k]) % mod;
            }
        }
    }
    for (int i = 0; i < 10; i++)
    {
        ans = (ans + dp[n][i][(1 << 10) - 1]) % mod;
    }

    cout << ans;
}

<hide/>
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int mod = 1000000000;
        long ans = 0;
        int[][][] dp = new int[101][10][1<<10];
        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=0; k<(1<<10); k++)
                {
                    if(j==0) dp[i][j][k | 1<<j] = (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][j][k | 1<<j] + dp[i-1][j-1][k]) % mod;
                    else dp[i][j][k | 1<<j] = (dp[i][j][k | 1<<j] + dp[i-1][j-1][k] + dp[i-1][j+1][k]) % mod;
                }
            }
        }
        for(int i=0; i<10; i++)
        {
            ans = (ans + dp[n][i][(1<<10)-1]) % mod;
        }
        System.out.println(ans);
    }
}