[백준] 9095번 1, 2, 3 더하기 (C++) - 간단한 dp

1. 발상

 간단한 dp를 이용해 문제를 해결했다.  

i의 합 -> (i-1)의 합 + (i-2) 의 합 + (i-3) 의 합 

base case -> (dp[1] = 1, dp[2] =2, dp[3] = 4) 로 설정한다.

 

2. 소스코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int dp[12] = {0, };

int main(){
	cin.tie(NULL); ios::sync_with_stdio(false);
	int T;
	cin >> T;

	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;

	for(int i=4; i<12; i++){
		dp[i] = dp[i-1] + dp[i-2] + dp[i-3]; 
	}

	for(int i=0; i<T; i++){
		int N;
		cin >> N;
		cout << dp[N] << "\n"; 
	}
}

 

dp 부분만 따로 보면 다음과 같다.

dp[1], dp[2], dp[3]의 base case 설정

-> for문으로 dp값 계산 후 배열에 채워넣기

	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;

	for(int i=4; i<12; i++){
		dp[i] = dp[i-1] + dp[i-2] + dp[i-3]; 
	}