[Baekjoon] 9095번: 1, 2, 3 더하기

🥅 문제

https://www.acmicpc.net/problem/9095

 

🔍 설계

1 = 1

2 = 1 + 1 = 2

3 = 1 + 1 + 1 = 2 + 1 = 1 + 2 = 3

4 = 1 + 1 + 1 + 1 = 2 + 1 + 1 = 1 + 2 + 1 = 3 + 1 = 1 + 1 + 2 = 2 + 2 = 1 + 3

으로 dp[i] = dp[i-1]+dp[i-2]+dp[i-3]이라는 것을 알 수 있다. dp[0]을 0으로 초기화하면, 1부터 반복문을 시작할 수 있다.

 

단, 범위를 주의해야 한다.

 

👊 풀이

#include <iostream>
#include <vector>
using namespace std;

int t, n;
vector<int> dp(11);

int main(void)
{	
	dp[0] = 1;
	for (int i = 1; i < 11; i++) {
		if (i - 1 >= 0) {
			dp[i] += dp[i - 1];
		}
		if (i - 2 >= 0) {
			dp[i] += dp[i - 2];
		}
		if (i - 3 >= 0) {
			dp[i] += dp[i - 3];
		}
	}
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		cout << dp[n] << "\n";
	}
	return 0;
}