백준 #1562 : 계단 수

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

백준 #10844 : 쉬운 계단 수를 먼저 풀어보자.

>>> 조합으로 풀어야하나 고민 참 많이 했고, dp를 어떻게 활용할 지 고민 많이 했는데,, 아주 간단한 점화식으로 해결 할 수 있었다... 계단 수의 접근은 쉬운 계단 수에 서술했다.

​

1. 브루트포스

각 자리마다 1씩 빼거나 더해가면서 flag 0, flag 9를 체크하고, (계단식이나까 0, 9 체크됐으면 다나온거임) 재귀돌리기

역시 시간초과,, 24자리 이상 힘들다.

​

2. DP와 비트마스킹

쉬운 계단 수를 풀었다면, 이제 계단 수에서 0~9를 사용했는지 안했는지 체크하면 된다. 이걸 체크하는데 비트 마스킹을 사용한다.

​

근데..! 여기서 문제가 생겼다... 나는 쉬운 계단수를 length 가 1일때를 모두 채워넣고

나보다 길이가 1 짧은 거에서, use가 똑같고 start-1로 시작하는거, start+1 로 시작하는걸 더하고,

start 사용하지 않은 use 이고 start-1, start+2 로 시작하는걸 더했다.

근데 start 를 사용하지 않은 use를 구하는데에서 문제가 생기는듯.

 

실패코드 1.

#include <iostream>
#include <vector>
using namespace std;

int N;
int save[10][101][1<<10]; // 0000000000 ~ 1111111111
int MOD = 1000000000;

int count(int start, int length, int use) {
	if (length == 0 ) return 0;
	if (start < 0 || start > 9) return 0;

	int& result = save[start][length][use];
	if (result != -1) return result;

	result = 0;
	result += count(start - 1, length - 1, use);
	result += count(start - 1, length - 1, use - (1 << start));
	result += count(start + 1, length - 1, use);
	result += count(start + 1, length - 1, use - (1 << start));

	result %= MOD;
	return result;
}


int main(int argc, char argv[]) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	memset(save, -1, sizeof(save));

	cin >> N;

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < (1 << 10); j++) {
			if (j == (1 << i)) save[i][1][j] = 1;
			else save[i][1][j] = 0;
		}
	}
	
	int sum = 0;
	for (int i = 1; i < 10; i++) {
		sum += count(i, N, (1 << 10) - 1);
		sum %= MOD;
	}
	cout << sum;
}

나보다 1 길고,

start-1이나 start+1 로 시작하고,

내 use에 그의 start가 포함된 use를 가진걸 더하면 된다..

​

그러면 길이가 a를 start 로 가지는걸 최종적으로 구할 수 있다...

​

초기값은 length == N 이고, use가 모두 1이면 1, 아니면 0.