코드업 3506번 입니다.
2x1의 직사각형 블럭을 이용하여 2xn 크기의 직사각형 모양으로 채우려고 한다.
가능한 방법의 수를 구하여라. 2x1 직사각형 블럭은 무한정 있다고 가정한다.
입력
첫 줄에 n이 입력된다. (1<=n<=30)
출력
2xn의 직사각형을 채울 수 있는 방법의 수를 출력하시오.
1. 문제분석
이 문제에서도 피보나치가 보입니다.
계속 쌓이다 보니 n = (n-1) + (n-2) 가 되는 것을 알 수 있죠.
그래도 그 과정을 그려보겠습니다.
2. 순서도
이제 이 순서도는 익숙한 것 같습니다.
3. 코딩
코딩을 하면?
#include <stdio.h>
int f(int n){
if(n==1) return 1;
if(n==2) return 2;
else return f(n-1)+f(n-2);
}
int main(){
int n;
scanf("%d", &n);
printf("%d", f(n));
}이렇게 됩니다.
전 글에서 n=1, n=2 일 때의 값만 바꿔주면 됩니다.
피보나치의 적용이 많은 것 같습니다.
그럼 다음 글에서 보겠습니다.
