🖊️ 문제

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

---

🖊️ 풀이

DP는 정말 노가다인것같다

각 방법의 수를 dp[i]라고 하면
dp[1] = 1
dp[2] = 3
dp[3] = 5
dp[4] = 11
dp[5] = 21
dp[6] = 43
dp[7] = 85
dp[8] = 171

하나하나 노가다해서 구한 뒤 규칙을 찾으면

i가 짝수인 경우는 이전 값 2 + 1
i가 홀수인 경우는 이전 값 2 - 1

굿굿냐 ..

#include <iostream>
using namespace std;

int arr[1001];

int main()
{
	int n;
	cin >> n;

	arr[1] = 1;

	for (int i = 2; i <= n; i++) {
		if (i % 2 == 0)
			arr[i] = (arr[i - 1] * 2 + 1) % 10007;
		else
			arr[i] = (arr[i - 1] * 2 - 1) % 10007;
	}
	cout << arr[n] << endl;
}