1562 ๊ณ„๋‹จ์ˆ˜

์•Œ๊ณ ๋ฆฌ์ฆ˜(DP, ๋น„ํŠธ๋งˆ์Šคํ‚น)

1. ์ˆซ์ž๋ฅผ ๊ธฐ๋กํ•˜๋Š” num[101] ๋ฐฐ์—ด๊ณผ, DP[101][10][1 << 10] ๋ฐฐ์—ด์„ ์ด์šฉํ•˜์—ฌ DP๋กœ ํ’ˆ
2. ์•ž์—์„œ๋ถ€ํ„ฐ ๊ธธ์ด์— ๋งž๊ฒŒ ์ˆซ์ž๋ฅผ ํ•˜๋‚˜ํ•˜๋‚˜ ๊ธฐ๋กํ•ด๊ฐ. ๊ธฐ๋กํ•˜๋ฉด์„œ ๋น„ํŠธ๋งˆ์Šคํ‚น์œผ๋กœ 0~9๊ฐ€ ์žˆ๋Š”์ง€ ํ‘œ์‹œ
	-> ์ด๋•Œ ์ด๋ฏธ ํ‘œ์‹œ๋œ ๋น„ํŠธ์— ๋˜ ํ‘œ์‹œํ•˜๋ฉด ๊ธฐ๋ก์ด ๋ง๊ฐ€์ง. ๋”ฐ๋ผ์„œ & ์—ฐ์‚ฐ์ž๋กœ ๊ฒ€์‚ฌํ•˜๊ณ  ๋„ฃ์Œ
		ex) int b = bit & (1 << num[deep]) ? bit : bit + (1 << num[deep]);
3. ๊ฒฐ๊ณผ๊ฐ’์€ DP[deep][num[deep-1]][bit] ์— ๊ธฐ๋กํ•˜์—ฌ DP๋ฅผ ๊ตฌํ˜„
	(num[deep-1] ์ธ ์ด์œ ๋Š” ๋‚ด ๊ตฌํ˜„์—์„  ํ˜„์žฌ deep์— ๊ธฐ๋ก์„ ํ•˜๊ณ  ๋‹ค์Œ deep์œผ๋กœ ๋„˜๊ธฐ๋ฏ€๋กœ num[deep]์œผ๋กœ ํ•˜๋ฉด ๊ธฐ๋ก์ด ๋ง๊ฐ€์ง„๋‹ค.)

์ฝ”๋“œ

#include <bits/stdc++.h>
#define MAX_LENGTH 100
#define DIV 1000000000
#define ALL 1023
 
using namespace std;
 
int N, num[101];
long long DP[101][10][1 << 10];
 
long long getAnswer(int, int);
 
int main() {
	cin >> N;
	memset(DP, -1, sizeof(DP));
 
	long long result = 0;
	for (int i = 1; i <= 9; i++) {
		num[0] = i;
		result += getAnswer(1, 1 << i);
	}
 
	cout << result % DIV << endl;
}
 
long long getAnswer(int deep, int bit) {
	if (deep == N) {
		if (bit == ALL)
			return 1;
		return 0;
	}
	if (DP[deep][num[deep - 1]][bit] != -1)
		return DP[deep][num[deep - 1]][bit];
 
	long long result = 0;
	if (num[deep - 1] != 0) {
		num[deep] = num[deep - 1] - 1;
		int b = bit & (1 << num[deep]) ? bit : bit + (1 << num[deep]);
		result += getAnswer(deep + 1, b);
	}
	if (num[deep - 1] != 9) {
		num[deep] = num[deep - 1] + 1;
		int b = bit & (1 << num[deep]) ? bit : bit + (1 << num[deep]);
		result += getAnswer(deep + 1, b);
	}
 
	return DP[deep][num[deep-1]][bit] = result % DIV;
}