[백준] C++ 9095(1,2,3 더하기)

 

#include <iostream>

using namespace std;

int DP[12];

int main(void)
{
	int a=0;
	cin>>a;
	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<a; i++)
	{
		int num=0;
		cin>>num;
		cout<<DP[num]<<endl;
	}
	
	return 0;
}

 

이 문제는 간단한 DP문제이다.

그림으로 설명해 보겠다.

DP[i]=DP[i-1]+DP[i-2]+DP[i-3]가 성립한다.

오른쪽에 숫자를 추가한다고 상상해 보자

 

DP[1]의 경우에는

1+3

DP[2]의 경우에는

1+1+2

2+2

DP[3]의 경우에는

1+1+1+1

2+1+1

1+2+1

3+1

 

DP[4]=1+2+4