[백준 1562] 계단 수

아이디어

• DP를 사용할 줄 안다
• 비트마스킹을 사용할 줄 안다

접근방식

1. DP를 위한 배열을 만들되, 배열은 [숫자의 길이],[마지막(1의자리) 수의 번호],[비트]를 가질 수 있게 저장한다. 여기서 '비트'는 '현재 숫자에서 찾을 수 있는 숫자는 1로 켠 비트' 로 설정한다. ex) 숫자가 13이면 0000001010 이 될 수 있다.
2. 3중 포문을 돌되, 숫자의 길이만큼 -> 숫자의 마지막에 넣어줄 숫자번호에 대해 -> 0 9개부터 1 9개까지의 비트에 대해 포문을 돌아준다
3. bit 포문을 돌면서, 현재 마지막으로 넣어줄 숫자 와 bit를 or 연산으로 묶어준다.
4. 그 묶어준 배열에 이전 숫자길이와 묶기전 비트를 더해준다. 단, 마지막 숫자가 0일때와 9일때를 개별로 만들어준다.

#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n; cin >> n;

	if (n <= 9) {
		cout << 0 << endl;
		return 0;
	}

	for (int i = 1; i <= 9; i++) {
		dp[1<<i][1][i] = 1;
	}
	//(int)10e8;
	for (int i = 2; i <= n; i++) { // i는 숫자 갯수
		for (int k = 0; k <= 9; k++) { // k는 마지막 숫자 번호
			for (int bit = 0; bit < (1 << 10); bit++) { // bit는 이전 비트
				if (k == 0) {
					dp[bit | (1 << k)][i][k] += dp[bit][i - 1][k+1] % (int)10e8;
				}
				else if (k == 9) {
					dp[bit | (1 << k)][i][k] += dp[bit][i - 1][k - 1] % (int)10e8;
				}
				else {
					dp[bit | (1 << k)][i][k] += (dp[bit][i - 1][k + 1] + dp[bit][i - 1][k - 1]) % (int)10e8;
				}
			}
		}
	}

	long long answer = 0;

	for (int i = 0; i <= 9; i++) {
		answer = (answer + dp[(1<<10) - 1][n][i]) % (int)10e8;
	}

	cout << answer << endl;

	
	return 0;
}

평가

비트마스킹과 dp를 이런식으로 사용가능하구나 라는 것을 알 수 있는 문제.
저는 0000000000 ~ 1111111111 비트까지 for문을 돌리는게 비효율적일 것 같아, 사용을 안하고있었으나, 다른 풀이가 떠오르지 않고, 메모리와 시간초과가 나지않고 충분히 풀 수 있을 것 같아 사용하였습니다.
이 문제에서 가장 중요한 풀이가 '선택한 숫자에서 고를 수 있는 숫자번호를 bit로 저장' 해주는 것이 KEY POINT이지 않을까 싶습니다.