백준 9095번 : 1, 2, 3 더하기

문제 링크 : www.acmicpc.net/problem/9095

내 풀이(2021.1.18.) :

#include <iostream>

using namespace std;

int sum(int n) {
	if (n == 1) return 1;
	if (n == 2) return 2;
	if (n == 3) return 4;
	return sum(n - 1) + sum(n - 2) + sum(n - 3);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T; cin >> T;
	for (int i = 0; i < T; i++) {
		int n; cin >> n;
		cout << sum(n) << endl;
	}

	return 0;

}

분석 : 재귀 함수(하향식) 이용, 메모이제이션 적용 X

 

내 풀이2(2021.1.18.) :

#include <iostream>
#include <string.h>

using namespace std;

int cache[11];

int sum(int n) {
	if (n == 1) return 1;
	if (n == 2) return 2;
	if (n == 3) return 4;
	if (cache[n] != -1) return cache[n];
	return cache[n] = sum(n - 1) + sum(n - 2) + sum(n - 3);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	memset(cache, -1, sizeof(cache));

	int T; cin >> T;
	for (int i = 0; i < T; i++) {
		int n; cin >> n;
		cout << sum(n) << endl;
	}

	return 0;

}

분석 : 재귀 함수(하향식) 이용, 메모이제이션 적용 O

 

내 풀이3(2021.1.18.) :

#include <iostream>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int sum[11];
	sum[1] = 1; sum[2] = 2; sum[3] = 4;

	int T; cin >> T;
	for (int i = 0; i < T; i++) {
		int n; cin >> n;
		if (n > 3) {
			for (int j = 4; j <= n; j++) {
				sum[j] = sum[j - 1] + sum[j - 2] + sum[j - 3];
			}
		}
		cout << sum[n] << endl;
	}

	return 0;
}

분석 : 반복문(상향식) 이용