[BAE/<JOON> 문제풀이] 1562. 계단 수

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

1562번: 계단 수

핵심::
DP 기본 문제

풀이::
골드 1 치고 점화식이 매우 간단하다.

거기다 힌트에 정답 여부를 거진 확정적으로 확인할 수 있는 내용을 적어놓아서 풀기가 수월했다.

점화식::
DP[n][m][k] = 길이가 n이고 마지막 숫자가 m이며 k의 비트마스크(2^10 - 1) 를 가진 계단수를 만들 수 있는 경우의 수

DP[n][m][k | 1 << m] += DP[n - 1][m - 1][k] + DP[n - 1][m + 1][k]

단, m이 0이거나 9인 경우 m - 1 / m + 1 이 불가능하므로 따로 처리해야 한다.

의견::
솔직히 점화식 난이도 골드3 이하

 

코드::

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int dp[101][10][1024];

const int mod = 1000000000;

int main()
{
	int n; cin >> n;
	if (n < 10) {
		cout << 0;
		return 0;
	}
	
	for (int i = 1; i <= 9; i++) {
		int bit = (1 << i);
		dp[1][i][bit] = 1;
	}

	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			for (int k = 0; k <= 1023; k++) {
				int bit = (k | (1 << j));
				int s1 = 0, s2 = 0;
				if (j > 0) {
					s1 = dp[i - 1][j - 1][k];
				}
				if (j < 9) {
					s2 = dp[i - 1][j + 1][k];
				}
				dp[i][j][bit] += (s1 + s2) % mod;
				dp[i][j][bit] %= mod;
			}
		}
	}

	int sum = 0;

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

	cout << sum;

	return 0;
}