백준 14606 c++ : DP

DP를 푸는 방법 중 규칙을 찾는 방법으로 풀이해봤다.

#include <iostream>
#include <vector>

using namespace std;

int find_answer(int N) {
	int answer = 0;
	vector<int> DP(N + 1);
	int i, j;
	/*
	* 8의 경우
	* 4, 4 => 16
	* 2, 2 / 2, 2 => 4 * 2 = 8
	* 1, 1 / 1, 1 / 1,1 /1,1 = 4
	* =>26
	* 즉 절반으로 나눌때 커짐?
	*/
	/*
	1 = 0
	2 = 1
	3 = 3
	4 = 6
	5 = 10
	6 = 15
	7 = 21
	8 = 28
	9 = 36
	*/
	DP[0] = 0;
	for (i = 1; i < DP.size(); i++) {
		if (i % 2 == 1)//홀수일때
		{
			//(이전 짝수 인덱스 값 / 2) * (현재 홀수 인덱스 값)
			DP[i] = (i - 1) / 2 * i;
		}
		else { //짝수일때
			//이전 홀수 값 + 이전 홀수 인덱스 값
			DP[i] = DP[i - 1] + (i - 1);
		}
		cout << DP[i] << " ";
	}
	answer = DP[N];

	return answer;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	
	cin >> N;
	cout << find_answer(N) << "\n";

	return 0;
}