백준 스트릭 81일차-1, 2, 3 더하기

#9095 - 1,2,3 더하기

문제 내용

• 처음에 테스트 케이스의 개수 T가 주어지고, T만큼 10 이하의 자연수 n이 주어질 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하시오.
• ex) n = 4라면 1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2, 3+1, 1+3 -> 7가지로 나타낼 수 있음.

접근 방법

• 자연수 n을 1,2,3으로 분리하는 모든 경우의 수를 구해야 함, 순서에 영향을 받음.
• 재귀 함수/탑다운 방식을 통해 이를 해결.

작동 원리

• 정수를 반환하는 함수에서 변수 first,second,third 3개를 관리 (각각 0으로 초기화).
• n = 0이라면 더 이상 수를 나눌 수 없다고 판단, 1을 반환.
• n>=1이라면 first = f(n - 1), n>=2이면 second = f(n - 2), n>=3이면 third = f(n-3) 호출.
• 3가지의 경우의 수를 모두 더하여 반환(return first + second + third).

소스 코드

#include<iostream>
using namespace std;

int sum(int n) { // n에서 1,2,3을 빼는 방식으로 경우의 수를 구함.
	int first = 0;
	int second = 0;
	int third = 0;

	if (n <= 0) // 더 이상 뺄 수 없으면?
		return 1;
	if (n - 1 >= 0)
		first = sum(n - 1); // n에서 1을 뺀 경우의 수
	if (n - 2 >= 0)
		second = sum(n - 2); // 2를 뺀 경우의 수
	if (n - 3 >= 0)
		third = sum(n - 3); // 3을 뺀 경우의 수

	return first + second + third; // 1,2,3 모든 경우의 수를 더한 값 반환
}
int main() {
	int n; // 10 이하의 자연수 n
	int t; // 테스트 케이스의 개수

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