1516 Developing game

์•Œ๊ณ ๋ฆฌ์ฆ˜(์œ„์ƒ์ •๋ ฌ, ๊ทธ๋ž˜ํ”„. DP)

1. ์–ด๋–ค ๊ฑด๋ฌผ์„ ์ง“๊ธฐ ์œ„ํ•ด ํ•„์š”ํ•œ ๊ฑด๋ฌผ์„ ์ง“๋Š” ์‹œ๊ฐ„์˜ ์ตœ๋Œ€ + ์ด ๊ฑด๋ฌผ์„ ์ง“๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์„ ์ถœ๋ ฅํ•˜๋ฉด ๋จ.
2. ์˜ˆ๋ฅผ ๋“ค์–ด
	A ->  	-> D
	      C
	B -> 	-> E
	๋กœ ๊ทธ๋ž˜ํ”„๊ฐ€ ์ด๋ฃจ์–ด์ ธ ์žˆ์„ ๋•Œ,

	A : A๋ฅผ ์ง“๋Š” ์‹œ๊ฐ„
	B : B๋ฅผ ์ง“๋Š” ์‹œ๊ฐ„
	C : max(A, B) + C๋ฅผ ์ง“๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„
	D : C + D๋ฅผ ์ง“๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„
	E : C + E๋ฅผ ์ง“๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„
	์ด๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.
	๋ฌผ๋ก  ๋ชจ๋“  ๊ฑด๋ฌผ์€ ์ง€์–ด์งˆ ์ˆ˜ ์žˆ๋Š” ์ƒํƒœ์ผ ๋•Œ ๋ฐ”๋กœ ์ง“๋Š” ๊ฒƒ์„ ๊ฐ€์ •ํ•œ๋‹ค.
3. ๋‚˜๋Š” ์ด๊ฑธ ๋ฌดํ•œ๋ฃจํ”„๋กœ ๋ชจ๋“  ๊ฑด๋ฌผ์„ ๊ฒ€์‚ฌํ•  ๋•Œ๊นŒ์ง€, ๋ชจ๋“  ๊ฑด๋ฌผ์„ ์ฒ˜์Œ๋ถ€ํ„ฐ ๋๊นŒ์ง€ ํ™•์ธํ•˜๋Š” ์‹์œผ๋กœ ๊ตฌํ˜„ํ•˜์˜€๋‹ค.
   ์ตœ๋Œ€ ๊ฑด๋ฌผ์˜ ์ˆ˜๊ฐ€ 500๊ฐœ์ด๋‹ˆ ์„ ํ˜•์ผ๊ฒฝ์šฐ ์ตœ์•… 25000์ด๊ธฐ์— ์ถฉ๋ถ„ํžˆ ์‹œ๊ฐ„์ด ๋งŽ๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.
   ํ•˜์ง€๋งŒ, ๋” ๋น ๋ฅธ ๋ฐฉ๋ฒ•์€ ์œ„์ƒ์ •๋ ฌ์„ ํ•˜์—ฌ ํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.
   ๊ทธ๋ž˜ํ”„๊ฐ€ ๊ทธ๋ ค์ ธ ์žˆ๋Š” ๋Œ€๋กœ ์ •๋ ฌ์„ ํ•˜์—ฌ์•ผํ•œ๋‹ค.
   ์˜ˆ๋ฅผ ๋“ค์–ด, ์œ„์˜ ์˜ˆ์—์„  A B C D E ์ˆœ์œผ๋กœ ์ •๋ ฌ์ด ๋˜์–ด์•ผํ•œ๋‹ค.
   ์ด๋ ‡๊ฒŒํ•˜๋ฉด, ๋ฌดํ•œ๋ฃจํ”„๋กœ ํ•  ํ•„์š”์—†์ด ์ฒ˜์Œ๋ถ€ํ„ฐ ๊ทธ๋ƒฅ ์‘ฅํ›‘์œผ๋ฉด์„œ ๊ฒ€์‚ฌํ•˜๋ฉด ๋๋‚˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

๊ธฐํƒ€

1. ์œ„์ƒ์ •๋ ฌ ํ•˜๋Š” ๋ฒ• ์•Œ์•„๋ณด๊ธฐ -> ์•Œ์•„๋ดค๋Š”๋ฐ ๊ตณ์ด ์œ„์ƒ์ •๋ ฌ ๋ฐฐ์—ด์„ ๋งŒ๋“ค ํ•„์š”๋Š” ์—†๋Š” ๊ฑฐ ๊ฐ™๋‹ค.
2. DP : ์™œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ถ„๋ฅ˜์— DP๊ฐ€ ๋“ค์–ด๊ฐ”๋‚˜ ํ–ˆ๋”๋งŒ, ์ด๋ฏธ ๊ฒ€์‚ฌํ•œ ๊ฑฐ๋Š” checkํ‘œ์‹œํ•˜์—ฌ ๊ฒ€์‚ฌํ•˜์ง€์•Š๊ณ , ์ตœ๋Œ“๊ฐ’์„ ๋‹ค์Œ ๋…ธ๋“œ๋กœ ๊ณ„์† ๋„˜๊ฒจ์ฃผ๋Š” ํ˜•ํƒœ๊ฐ€ DP์ธ๊ฑฐ ๊ฐ™๋‹ค.

์ฝ”๋“œ

#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;
}