[구름 알고리즘 먼데이 챌린지] Week4 : 4. 주차 구역 나누기

DP유형의 문제라는 것을 파악하고 점화식을 찾기 위해 하루 꼬박 투자했지만 결국 점화식을 구하지 못하고 해설을 봤다.

문제 난이도가 너무 높다고 느껴졌고 해설을 보고서도 이해하는데 굉장히 오래걸렸다.

해설에 파이썬 코드를 c++언어로 아래와 같이 작성했다.

 

#include <iostream>
#include <deque>
using namespace std;

int n;
deque<long long> dp;

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	dp.push_back(0);
	dp.push_back(0);
	dp.push_back(1);

	for (int i = 3; i <= n; i++) {
		int last = dp.size() -1;
		dp.push_back( (2 * (i - 1) + 1) * dp[last] + dp[last - 1] );
		dp.pop_front();
	}
	cout << dp.back() % 100000007;
}

내 생각엔 해설 코드와 같은 로직이라고 생각했는데 TC1, 2, 3을 제외하고 FAIL로 나왔고 1:1 문의를 넣고 답변을 기다리고 있다.