BOJ1562 계단수/C++

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

1562번: 계단 수

백준 온라인저지 1562번 계단수 문제입니다.

#include<iostream>

#define MAX 101
#define numMax 10
#define MOD 1000000000
using namespace std;

int n;

long long dp[MAX][numMax][1 << 10];
void Input() {
	cin >> n;
}

void solution() {
	for (int i = 1; i <= 9; i++) {
		dp[1][i][1 << i] = 1;
	}


	for (int k = 2; k <= n; k++) {
		for (int i = 0; i <= 9; i++) {
			for (int bit = 0; bit < (1 << 10); bit++) {

				// k의 i번째 bit를 on 시킨다

				// n자리 + i로 끝나고 + 기존 k 상태(여태 사용한 숫자의 모음)에서 숫자 i를 추가하는 경우는
				// n-1자리 + i-1 or i+1로 끝나고 + 기존 상태의 값(숫자 i를 추가하지 않음) 을 더해줘야 한다
				if (i == 0) {
					dp[k][i][bit|(1<<i)] += dp[k - 1][i+1][bit] % MOD;
				}
				else if (i == 9) {
					dp[k][i][bit|(1<<i)] += dp[k - 1][i-1][bit] % MOD;
				}
				else {
					dp[k][i][bit|(1<<i)] += (dp[k - 1][i - 1][bit] + dp[k - 1][i + 1][bit]) % MOD;
				}
			}


		}
	}

	long long cnt = 0;
	for (int i = 0; i <= 9; i++) {
		cnt =(cnt + dp[n][i][(1 << 10) -1]) % MOD;
	}
	cout << cnt;
}

int main(void) {
	Input();
	solution();
}

아이디어

이전에 비슷한 유형의 문제를 풀었던 경험이 있다.

비트필드를 사용하지 않는 문제인 쉬운계단수 와 2021 카카오코테에서 다익스트라에서 비트필드를 이용하여 풀었던

문제가 있는데 적당히 조합해서 풀이 하였음

dp[숫자의 개수][자리수][비트필드(숫자 사용 상태)]로 점화식을 새웠고, 마지막에 모든 숫자를 사용한 생태의 모든 자릿수를 더해주었음