C++ 백준 1562 (계단 수)

백준 1562 (계단 수)

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

1562번: 계단 수

---

DP와 재귀에 비트마스크 연산을 사용하여 풀 수 있는 문제이다.

때문에 이 문제를 해결하기 위해선 DP, 재귀호출, 비트마스크 연산에 대한 이해가 필요하다.

 

설명

---

계단 수의 기본적인 아이디어는 다음과 같다.

시작숫자를 특정 숫자로 고정한 뒤, 재귀호출을 통해 이어나아갈 수 있는 숫자를 붙여 입력 N의 길이가 되면 멈추는 방식이다.

그러나 이 문제는 한 가지 조건이 더 있다. 0~9까지 모든 숫자가 포함되어야 한다는 것이다.

 

0~9까지 모든 숫자가 있는지 없는지를 판단한다.. 있는지 없는지..

공학에서 있다 없다는 0과 1로 표현이 가능하다. 무엇이 떠오르지 않는가? 바로 2진수이다.

예를들어 4자리 숫자에서 0,1,3은 포함이 되어있고 2가 포함되어있지 않다면 그 수의 포함숫자 여부는 1011로 표현될 수 있을것이다.

그리고 만약 그 숫자에 어떤 과정을 거쳐 2가 포함이 되게 된다면 1011 | (1<<2)를 취하면 될것이다.

(이해가 되지 않는다면 비트마스킹에 대해 공부하고 오자)

 

0~9까지 모든 숫자를 포함하라는 조건이 없다면 간단히 2차원 DP배열을 통해 원하는 답을 얻을 수 있을 것이다. 그러나 조건이 추가되었으므로 각 숫자여부를 판단할 수 있는 배열이 하나 추가되어야 한다.

즉 이문제를 풀기위해선 3차원 DP배열이 필요하다.

 

DP[10][101][1024] = DP[현재자리의 숫자][현재 자리 수][0~9 숫자 포함여부]를 선언한다.

이제 0~9숫자 포함여부를 비트라고 표현하겠다.

 

첫 자리를 특정 숫자 i로 고정하고 숫자 포함여부(1<<i)를 가진채로 자리수를 늘려가며 재귀를 시작한다.

자리수가 하나 늘어갈 때마다 이전 숫자에 +1이나 -1을 해가며 계속 재귀를 돌린다. 만약 2다음 1또는 3이 나온다고 할때 현재비트에 1<<1 이나 1<<3을 OR연산시켜주면 되는 것이다.

현재 자리수가 입력 N과 같아질 때 만약 비트가 1023이라면 0~9까지 모든 수를 포함하는 것이므로 1을 리턴해주고 (하나를 찾았다) 아니라면 0을 리턴한다.

 

구현

---

#include <iostream>
#define DIV 1000000000
using namespace std;
int dp[10][101][1024];
int N;
int go(int num, int digit, int bit){
    if(dp[num][digit][bit]!=0) return dp[num][digit][bit];
    if(digit==N){
        if(bit==1023) return 1;
        else return 0;
    }
    int tmp=0;
    if(num<9){
        int des = num+1;
        tmp+=go(des,digit+1,(bit|1<<(des)));
    }
    if(num>0){
        int des = num-1;
        tmp+=go(des,digit+1,(bit|1<<(des)));
    }
    tmp%=DIV;
    return dp[num][digit][bit]=tmp;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    
    cin>>N;
    int ans=0;
    for(int i=1;i<=9;i++){
        ans+=go(i,1,1<<i);
        ans%=DIV;
    }
    cout<<ans;
 
    return 0;
}

MOD연산은 그냥 알아서 한다.