백준 C++ 9095번 1, 2, 3 더하기

문제 바로가기(출처) : https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

설명

백준 9095문제 다이나믹 프로그래밍 문제입니다.

점화식을 이용하여 풀면 되겠습니다.

DP[i] = DP[i-1] + DP[i-2] + DP[i-3]

 

코드

#include <iostream>
using namespace std;

int dp[1000] = {};
int n, k;

int DP(int j){
	for(int i = 3; i<=j; ++i){
		dp[i]=dp[i-1] + dp[i-2]+dp[i-3];
		dp[j]=dp[i];
	}
	return dp[j];
}

int main(){
	cin >> n;
	dp[0] = 1;
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;
	int j;
	for(int i=1; i<=n; i++){
		cin >> j;
		cout << DP(j) << '\n';
	}
}

 

 

결과

 

지적 및 개선사항은 언제든지 댓글로 부탁드립니다!