[백준 알고리즘] 1562번 계단 수 c++

 

dp와 비트마스크를 활용한 문제.

배열 dp[x][y][z]에서 x는 계단수의 길이, y는 0~9인 숫자, z는 비트마스크로 사용된 숫자를 체크한다.

길이가 1이면서 숫자 1~9가 사용되었을 때 dp를 채운다

(0으로 시작하는 수는 계단수가 아니므로 0은 제외)

 

길이가 2~n일때(len for문)

숫자 0~9에 대해(num for문)

비트마스크 0000000000~1111111111일 때(i for문)

dp값을 채운다.

i for문에서 해당 비트마스크를 순차탐색하여 dp를 채울 수 있는 이유는

길이가 1일때, dp[1][1][2], dp[1][2][4], dp[1][3][8]...이 1이고,

길이가 2일때, dp[2][0][3], dp[2][1][6], dp[2][2][1], dp[2][2][12]...이 2가 되는 것처럼

BFS와 같이 순차적으로 채워지기 때문이다.

 

i가 0~9일때 dp[n][i][1023] 값을 다 더하면 원하는 계단 수를 구할 수 있다.

 

* 모듈러 연산은 (a+b)%m = a%m + b%m이다

정수 범위 내로 정답을 얻기 위해 dp값을 채우는 도중에 %1000000000을 한다. 

 

 

#include <iostream>

using namespace std;

int dp[101][10][1<<10];

int main(){
	int n;
	int mod = 1000000000;
	
	cin >> n;

	for(int i=1; i<10; i++)
		dp[1][i][1<<i] = 1;

	for(int len=2; len<=n; len++){
		for(int num=0; num<10; num++){
			for(int i=0; i<1024; i++){
				if(num != 0)
					dp[len][num][i | (1<<num)] = (dp[len][num][i | (1<<num)] + dp[len-1][num-1][i]) % mod;
				if(num != 9)
					dp[len][num][i | (1<<num)] = (dp[len][num][i | (1<<num)] + dp[len-1][num+1][i]) % mod;
			}
		}
	}

	int count = 0;
	for(int i=0; i<10; i++){
		count = (count+dp[n][i][1023]) % mod;
	}

	cout << count;
	return 0;
}