[Algorithm]Baekjoon 1562번 :: 계단 수

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

1562번: 계단 수

using namespace std;
 
int n;
int dp[101][10][1024] = { 0 }; // 자리수, 현재숫자, 비트
const int MOD = 1000000000;
 
int DFS(int digit, int num, int bit)
{
    if (dp[digit][num][bit] != 0)
    {
        return dp[digit][num][bit];
    }
 
    if (digit == n) // 자리수 맞췄고, 모든 숫자 다 사용했으면 
    {
        if (bit == 1023) return 1;
        else return 0;
    }
 
    int result = 0;
 
    if (num < 9)
    {
        result += DFS(digit + 1, num + 1, bit | (1 << (num + 1)));
    }
 
    if (num > 0)
    {
        result += DFS(digit + 1, num - 1, bit | (1 << (num - 1)));
    }
 
    result %= MOD;
    return dp[digit][num][bit] = result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    int answer = 0;
    for (int i = 1; i <= 9; ++i)
    {
        answer += DFS(1, i, 1 << i);
        answer %= MOD;
    }
 
    cout << answer;
}
 
 

 

처음 풀어보는 유형의 dp문제였다.. 풀이랑 코드보고도 바로 이해하지 못했었지만, 지금은 완전히 이해가 됐다.

주어진 n자리수를 채워야 하며, 각 양옆의 숫자는 1을 초과하게 차이나면 안된다. 그리고 결정적으로 0~9의 모든 숫자가 사용되어져야 한다.

 

여기서 0~9의 숫자가 모두 사용되었는지를 체크하기위해 비트마스킹 개념이 사용된다.

각 비트가 숫자의 사용유무를 의미한다. 여기서 사용되어지는 숫자는 0~9, 즉 총 10개이기 때문에 3차원배열크기를 1024로 한다. 

현재차례에서 모든 숫자가 사용되어졌다면, 11111 11111 이렇게 총 10개가 사용되어졌다고 표현되어질 수 있는데, 이때 10개의 비트가 전부 1이라면 정수값으로 1023이 된다. 그렇기 때문에 배열크기는 1024이고, 최대값은 1023이 된다.

 

DFS함수내에 or연산자를 이용한 표현이 있는데, 이건 bit값에 그대로 합연산을 해주는거랑 같은 의미이다.

위의 코드의 24번째 줄에서, bit | 1 << (num+1) 이라는 코드가 있는데 이것은 bit += 1 << (num+1)과 같은 의미이다.

이게 정수로표현해야해서 이렇게 표현하는것이고, 만약 bit가 10자리의 bit를 표현하는 변수라면, num+1번째 차례의 비트를 킨다는 의미이다.

이것은 결국 해당값을 더하는것과 마찬가지다. 그리고 or연산이기 때문에, 이미 켜져있다면 추가로 더하지 않는다.

즉 1 2 3 2 1  <-- 이렇게 진행됐을 경우, 2는 총 2번이 나오지만 or연산이기 때문에 해당 bit가 켜지는 과정자체는 한번만 수행된다. 그러니 bit값이 1023이면 무조건 모든 bit가 켜져있다는게 보장되어진다.

 

내 이해가 주목적이라 두설없이 쓴게 없지않아 있지만, 비트마스킹을 선행학습하고 다른사람풀이를 보면 이해가 갈 것이다.