좋아요 꾸준히 코딩을 해봅시다.
이번엔 코드업 2653번을 풀어볼게요
다음 두 가지 규칙을 지키면서 이진수를 만들고자 한다. 가능한 서로 다른 이진수의 개수를 구하는 프로그램을 작성하시오.
규칙1) 길이는 n이다.
규칙2) 0이 연속으로 존재하면 안된다.
예를 들어 길이가 3이라면, 길이가 3인 이진수는 다음과 같이 000, 001, 010, 011, 100, 101, 110, 111 8가지이다. 이 중 0이 연속으로 사용된 3개를 제외한 010, 011, 101, 110, 111 의 5가지가 답이다.
입력
이진수의 길이를 나타내는 자연수 n이 입력된다.
[입력값의 정의역]
1≤n≤20
출력
가능한 경우의 수를 출력한다.
1. 문제분석
규칙 2를 빼고 생각했을 때는 '오? 이것도 조합관련한 문제 아닌가?' 라고 생각했지만
0이 연속으로 있는 경우는 빼야되더군요..
규칙을 찾기 위해 n이 1, 2, 3일 때의 경우를 살펴보았습니다.
나오는 조합들의 상황을 분석해볼게요.
n이 1일 때는 자릿수가 1 뿐이니 제외할 경우가 없으니 2개,
n이 2일 때는 00일 때를 제외한 3개 입니다.
이제 규칙을 찾아야 하는 n=3일 때를 보도록 하죠.
000, 001일 때, 앞에 00을 빼고 보면 n=1과 같지만 0이 연속입니다.
1이 한 쪽 끝에 있기 때문에 가능하지 않습니다.
010, 011일 때, 두번 째 자릿수에서 1이 분리를 해주어 n=1과 같습니다.
100일 때, 앞에 1을 빼면 n=2 일 때의 00과 같지만 조건과 맞지 않고
101, 110, 111은 n=2와 같습니다.
오호.....피보나치 수열 느낌이 나고 있습니다.
n=1, n=2 일 때만 설정주고 피보나치 수열의 점화식인
n = (n-1) + (n-2)
를 사용해보도록 하겠습니다.
2. 순서도
3. 코딩
바로 코딩을 해보면
#include <stdio.h>
int f(int n){
if(n==1) return 2;
if(n==2) return 3;
else return f(n-1)+f(n-2);
}
int main(){
int n;
scanf("%d", &n);
printf("%d", f(n));
}이렇게 됩니다.
방법만 찾으면 점화식으로 간단하게 풀 수 있는 문제였습니다!
그럼 다시 찾아오겠습니다.
