[BOJ 15989] 1, 2, 3 더하기 4

- 문제 요약

 

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

합을 나타낼 때는 수를 1개 이상 사용해야 하며, 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

(테스트케이스의 수 T가 주어진다. n은 양수이며 10,000보다 작거나 같다.)

 

 

- 알고리즘 정리

 

DP 문제입니다.

 

DP[X][a] (정수 X를 만들 때 a로 끝나는 경우의 수)
DP[i][1] = DP[i-1][1]
DP[i][2] = DP[i-2][1] + DP[i-2][2]
DP[i][3] = DP[i-3][1] + DP[i-3][2] + DP[i-3][3]

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 10001
int t,n,dp[MAX][4],num;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>t;
	dp[0][1]=dp[1][1]=1;
	for(int i=2;i<=10000;i++){
		dp[i][1]=dp[i-1][1];
		dp[i][2]=dp[i-2][1]+dp[i-2][2];
		if(i>=3){
			dp[i][3]=dp[i-3][1]+dp[i-3][2]+dp[i-3][3];
		}
	}
	num=3;
	while(t--){
		cin>>n;
		cout<<dp[n][1]+dp[n][2]+dp[n][3]<<endl;
	}
}

코드 제출 결과