[BOJ] 1562 계단 수

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

1562번: 계단 수

알고리즘: DP

 

시간복잡도: O(N^2 * 2^10) 

 

https://moon323.tistory.com/12

쉬운 계단 수의 심화문제이다.

 

0~9까지 모든 수가 자리수에 등장 이라는 조건만 추가되었다.

 

조합을 묻는 문제에서 on / off (등장, 비등장)을 묻는 문제는 비트연산을 이용해주면 빠르고 깔끔하게 해결 가능하다.

 

예를 들어, 이 문제 같은 경우 10bit를 만들어서 등장하는 수가 있으면 해당 bit를 1로 켜주면 된다. (or 연산)

ex) 

b = 0000000000

1) 1 등장: b | (1<<1) = 0000000010

2) 8 등장: b | (1<<8) = 0100000010

3) 0 등장: b | (1<<0) = 0100000011

 

D[i][j][b]: 자리 수가 i고 맨 마지막 수가 j이고, 자리수 조합이 b인 계단 수의 개수

 

$$답=\ \sum_{k=0}^9 D[N][k][2^{10}-1]\ mod\ 10^9$$

 

// 1562 계단 수
// fail 1: MOD 연산 잘못함
#include<iostream>
#include<bitset>
#define MOD 1000000000
using namespace std;

int N, D[101][10][1<<10];
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	
	for (int i = 1; i < 10; i++)
		D[1][i][1<<i] = 1;

	for (int i = 2; i <= N; i++)
	{
		for (int b = 1; b < 1024; b++)
		{
			D[i][0][b | 1] = (D[i][0][b | 1] + D[i-1][1][b])%MOD;
			D[i][9][b | (1<<9)] = (D[i][9][b | (1<<9)] + D[i-1][8][b])%MOD;
		}

		for (int j = 1; j < 9; j++)
		{
			for (int b = 1; b < 1024; b++)
			{
				D[i][j][b | (1<<j)] = (D[i][j][b | (1<<j)]+ D[i-1][j-1][b])%MOD;
				D[i][j][b | (1<<j)] = (D[i][j][b | (1<<j)]+ D[i-1][j+1][b])%MOD;
			}
		}
	}

	for (int i = 1; i < 10; i++)
		D[N][0][(1<<10)-1] = (D[N][0][(1<<10)-1] + D[N][i][(1<<10)-1])%MOD;
	
	cout << D[N][0][(1<<10)-1];
	return 0;
}