백준(Baekjoon)_9095번 문제풀이

 

 

다이나믹 프로그래밍에서 정답비율 좀 높길래 도전.

근데 어려운편.

첨에 재귀느낌이 왔지만

방학동안 머리를 안쓰니 '재귀 사용해야할 것 같은데 이제부터 어떻게 해야되는거지.' 이러다

결국 몇몇 블로그를 참고하고 난 후 

'아 이게 재귀였지.' 하고 풀었다.

 

 

#include <stdio.h>
int f(int n)//순서 상관있는 것에 유의하며 세기
{
    int count = 0;
    if(n == 1)
        return count += 1;//1이되는 경우의수 : 1
    else if(n == 2)
        return count += 2;//2가되는 경우의수 : 1+1,2
    else if(n == 3)
        return count += 4;//3이되는 경우의수 : 1+1+1,2+1,1+2,3
    else
        return f(n-3)+f(n-2)+f(n-1);//1,2,3만 사용하랬으니 이것을 이용하여 재귀함수만들기
}
int main(void)
{
    int i, k;//k로 숫자를 몇번 입력받을 건지 알아냄
    int n;//숫자입력
    int n2;//경우의 수 개수
 
    scanf("%d", &k);
 
    for(i = 0 ; i < k; i++){
        scanf("%d", &n);
        n2 = f(n);//경우의 수 리턴한 값 저장
        printf("%d\n", n2);
    }
}

count에 경우의 수를 저장시켜주고 이것을 서로 더해주는 식으로 풀었다.

그냥 간단하게....

 

 

/0114