1,2,3을 이용하여 값 구하기

정수 n을 1,2,3 조합으로 더하여 나타내는 가짓수를 t라 할때,

이때 n을 입력하였을 때 t를 출력하는 코드를 작성하라.

이때 정수 n은 양수이다.

ex) 

n = 3이면

1 + 1 + 1 = 3 

1 + 2 = 3     

2 + 1 = 3     

3 = 3         

총 4가지이다.

#include <stdio.h>
 
int cnt=0;
void repeat(int n)
{  
    if(n == 0) cnt++;
    if(n - 3 >= 0) repeat(n - 3);
    if(n - 2 >= 0) repeat(n - 2);
    if(n - 1 >= 0) repeat(n - 1);    
}
 
int main()
{
 int num;
 int i; 
 
  scanf("%d",&num);   
 
  repeat(num);
  
  printf("%d\n",cnt);
  cnt = 0;
 
 return 0;
}
 
 
 

재귀함수를 이용한다면 간단히 풀리는 알고리즘이다.

repeat라는 재귀함수를 통해 가장 큰 3값부터 이용하여 2,1순으로 재귀함수를 구현한다.

마지막에 n이 0이면 가짓수를 나타내는 cnt변수를 +1 해줌으로써

총 가짓수를 구할 수 있게 된다.