12849 ๋ณธ๋Œ€์‚ฐ์ฑ…

์•Œ๊ณ ๋ฆฌ์ฆ˜(DP)

1. a๋ผ๋Š” ๊ฑด๋ฌผ์— x๋ถ„์„ ๋‚จ๊ธฐ๊ณ  ๋“ค์–ด๊ฐ€๋Š” ๊ฒƒ์€, a์— ์—ฐ๊ฒฐ๋œ ๋ชจ๋“  ๊ฑด๋ฌผ b์— x+1๋ถ„์„ ๋‚จ๊ธฐ๊ณ  ๋“ค์–ด์˜จ ๊ฒƒ๊ณผ ๊ฐ™์Œ
2. ์ฆ‰, ์ •๋ณด๊ณผํ•™๊ด€์— 0๋ถ„์„ ๋‚จ๊ธฐ๊ณ  ๋“ค์–ด์˜ค๋Š” ๊ฒƒ์„ ์‹œ์ž‘์œผ๋กœ ๋ชจ๋“  ๊ฒฝ์šฐ๋ฅผ ํƒ์ƒ‰ํ•˜๋ฉด ๋œ๋‹ค.
3. ์ญ‰์ญ‰ ๋‚ด๋ ค๊ฐ€๋‹ค๊ฐ€ D๋ถ„์— ๋„๋‹ฌํ–ˆ์„๋•Œ, ์žฅ์†Œ๊ฐ€ ์ •๋ณด๊ณผํ•™๊ด€์ด๋ฉด 1, ์•„๋‹ˆ๋ฉด 0์„ ๋ฆฌํ„ดํ•˜์—ฌ ๋ฐ”ํ…€์—…์œผ๋กœ ํ•จ
4. DP์—๋Š” ํ˜„์žฌ ์œ„์น˜์™€ ์‹œ๊ฐ„์œผ๋กœ ๋ฐฐ์—ด์„ ๋งŒ๋“ค๊ณ , ๊ทธ ์œ„์น˜์—์„œ ๊ทธ ์‹œ๊ฐ„์ด ๊ฑธ๋ ธ์„ ๋•Œ์˜ ๊ฒฐ๊ณผ๋ฅผ 1000000007๋กœ ๋‚˜๋ˆˆ ๊ฐ’์„ ์ €์žฅํ•จ

์ฝ”๋“œ

#include <iostream>
#include <vector>
#include <cstring>
#define MAX_MINUTE 100000
#define DIVIDE 1000000007
 
using namespace std;
 
//0 : ์ •๋ณด, 1 : ์ „์‚ฐ, 2 : ๋ฏธ๋ž˜, 3 : ์‹ ์–‘ , 4: ํ•œ๊ฒฝ์ง,
//5 : ์ง„๋ฆฌ, 6 : ํ˜•๋‚จ, 7 : ํ•™์ƒ
vector<vector<int>> map = { {1,2}, {0,2,3}, {0,1,3,4}, {1,2,4,5}, {2,3,5,6}, {3,4,7}, {4,7}, {5,6} };
int D;
int DP[8][MAX_MINUTE];
 
int getMin(int num, int minute);
 
int main() {
	memset(DP, -1, sizeof(DP));
	cin >> D;
	cout << getMin(0, 0) << endl;
}
/*
a ์— x๋ฅผ ๋‚จ๊ธฐ๊ณ  ๋“ค์–ด์˜ค๋Š” ํšŸ์ˆ˜๋Š”
	a์™€ ์—ฐ๊ฒฐ๋œ ๋ชจ๋“  b์— x+1๋ฅผ ๋‚จ๊ธฐ๊ณ  ๋“ค์–ด์˜ค๋Š” ํšŸ์ˆ˜์™€ ๊ฐ™์Œ
*/
 
int getMin(int num, int minute) {
	if (minute == D)
		return num == 0 ? 1 : 0;
	if (DP[num][minute] != -1)
		return DP[num][minute];
 
	long long result = 0;
	int length = map[num].size();
	for (int i = 0; i < length; i++)
		result += getMin(map[num][i], minute + 1);
 
	return DP[num][minute] = result % DIVIDE;
}