[9095] 1,2,3 더하기

풀이

구해야할 것 : 정수 n을 1,2,3의 합으로 나타내는 방법

정수 n을 1,2,3으로 나타낼 때 가장 마지막에 적는 숫자를 생각해보면 1,2,3 세 가지 경우 뿐입니다.

코드

#include <iostream>

int dp[1000001];
int n,t;

int main(void) {
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		for (int i = 4; i <= n; i++) {
			dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
		}
		printf("%d\n", dp[n]);
	}
	
	return 0;
}