[백준 9095] 1, 2, 3 더하기 반복문 풀이, 재귀적 풀이

# 문제 링크

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

문제

 

# 풀이방법

 

문제 예시로 나온 4를 보면, 4를 만들기 위해서는 3을 만든거에 1을 더하고, 2에다가 2를 더하고, 1에다가 3을 더하면 된다. 

따라서 n 번째 숫자를 만드는 방법의 수는 n-1, n-2, n-3 를 만드는 법의 합이 된다. n 이 최대 11로 숫자가 크지 않기 때문에, 재귀로 풀어도 되고 - 반복문으로 풀어도 된다.

 

# 반복문 풀이 방법

 

#include <iostream>
using namespace std;
int d[15];
int main(){
	int t;
	cin >> t;
	d[1] = 1;
	d[2] = 2;
	d[3] = 4;
	for(int i =4; i<=11; i++){
		d[i] = d[i-1]+d[i-2]+d[i-3];
	}
	while(t--){
		int n;
		cin >> n;
		cout << d[n] << '\n';
	}
	return 0;
}

 

# 재귀 풀이 방법

 

#include <iostream>
using namespace std;
int d[15];
int solve(int n) {
	if (n<=3) return d[n];
	return solve(n-1) + solve(n-2) + solve(n-3);
}
int main(){
	int t;
	cin >> t;
	d[1] = 1;
	d[2] = 2;
	d[3] = 4;
	while(t--){
		int n;
		cin >> n;
		cout << solve(n) << '\n';
	}
	return 0;
}