백준 1562 - 계단 수(C++)

문제 링크입니다.https://www.acmicpc.net/problem/1562

1562번: 계단 수

비트마스킹과 Dp를 사용하는 문제입니다.

생각하는게 어려웠던 문제입니다.

 

0~9를 모두 포함하는 계단 수를 세는 문제입니다.

0~9를 사용했는지 배열을 이용해서 구하는 방법은 너무 어려워집니다.

따라서 변수 하나를 통해 0~9를 사용했는지 저장할 것입니다. -> 비트마스킹 방법을 사용하면 됩니다.

 

문제에 사용된 비트마스킹은 다음과 같습니다.

9	8	7	6	5	4	3	2	1	0
1	1	1	1	0	0	0	0	0	0

예를 들어, 계단 수가 10206789 라고 하면, (6, 7, 8, 9)가 계단수가 됩니다.

따라서 (6, 7, 8, 9)의 자리에 1를 저장해주는 것입니다.

그렇다면 나올 수 있는 최댓값은 모든 수를 사용한 1111111111 이 되며, 이는 2^10-1인 1023이 되는 것입니다.

 

이를 바탕으로 사용할 배열을 만들 것인데,

int dp[101][10][1<<10]; // i자리 숫자 중, j로 끝나며, K에 마킹 된 숫자들을 쓴 계단수 갯수

ex) dp[3][2][15] = 2자리 숫자 중, 2로 끝나며, 15(0000001111)에 마킹된 숫자들을 사용
                   -> 432
    dp[2][2][15] = 2자리 숫자 중, 2로 끝나며, 15(0000001111)에 마킹된 숫자들을 사용
                   -> 32, 12

이를 바탕으로 점화식을 유도하겠습니다.

길이가 N일 때는 N-1의 길이를 가진 값으로부터 값을 유도할 수 있습니다.

이때, X로 끝나는 수를 원한다면, X+1 or X-1로 부터 값을 가져오면 됩니다.(3 -> 2와 4로 가져올 수 있습니다.)

 

그렇다면, dp[N][X][K]는 dp[i-1][N-1][K] + dp[i-1][N+1][K] + 1(N = 1인 경우)로 구할 수 있습니다.

 

이때 주의할 점은, X가 0 or 9일 경우입니다. X가 0일 때는 -1에서 값을 가져올 수 없으며, 9인 경우에는 10에서 값을 가져올 수 없습니다. 따라서, 이를 따로 조건으로 분류해서 구해줘야 합니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#define LL long long
#define pp pair<int, int>
#define P pair<pp, pp>
#define F first
#define S second
#define mod 1000000000

using namespace std;

int N, ans;
int dp[101][10][1<<10];

void solve(){
    int Max = (1 << 10) - 1;
    for(int i = 1; i <= 9; i++){
        dp[1][i][1 << i] = 1;
    }
    for(int i = 1; i <= N; i++){
        for(int j = 0; j <= 9; j++){
            for(int k = 0; k <= Max; k++){
                if(j == 0){
                    dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][1][k]) % mod;
                }
                else if(j == 9){
                    dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][8][k]) % mod;
                }
                else{
                    dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i-1][j-1][k]) % mod;
                    dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i-1][j+1][k]) % mod;
                }
            }
        }
    }
    for(int i = 0; i<= 9; i++){
        ans += dp[N][i][Max];
        ans %= mod;
    }
    cout << ans;
}

int main() {
    cin.tie(0);
	cout.tie(0);
	cin >> N;
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요