9095 1,2,3 더하기

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int N;
int n;
int ret;
void init()
{
	N = n=0;
	scanf("%d", &N);
}
void dfs(int idx, int sum) {
	if (idx > n) return;//범위 넘어가는경우
	if (sum > n)return;
	if (sum == n) {
		ret++;
		return;
	}
	dfs(idx + 1, sum + 1);
	dfs(idx + 1, sum + 2);
	dfs(idx + 1, sum + 3);
}
int main(void) {
	init();
	for (int i = 0; i < N; i++) {
		ret = 0;
		scanf("%d", &n);
		dfs(0, 0);
		cout << ret<<endl;
	}
	return 0;
}

예전에 풀었던 방식이 위

#include<stdio.h>
#include<iostream>
using namespace std;
int n;//전체 입력 수
int cnt;//현재 나오는 조합 수
void dfs(int idx, int sum, int num) {
	if (sum >= num) {
		if(sum==num)cnt++;// num 조합이 되는 경우
		return;
	}
	for (int i = 1; i <= 3; i++) {
		dfs(idx, sum + i, num);
	}
}
int main(void) {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int num;//입력 숫자
		scanf("%d", &num);
		dfs(0,0,num);
		cout << cnt << endl;
		cnt = 0;
	}

	return 0;
}

다시 설계해서 구현한 방식 

 

방식은 여러가지 입니다. 그래서 여러방식으로 적용해보는것이 중요합니다.