2653 : 규칙에 맞는 이진수 만들기 (Small)

안녕하세요. 뇌 잃은 소 입니다.
 
오늘은 또 다른 코드업 문제를 들고 와 봤는데요.
 
 
2653 : 규칙에 맞는 이진수 만들기 (Small)
 
문제설명

다음 두 가지 규칙을 지키면서 이진수를 만들고자 한다. 가능한 서로 다른 이진수의 개수를 구하는 프로그램을 작성하시오.

규칙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

 
출력

가능한 경우의 수를 출력한다.

 
입력 예시

3

 
출력 예시

5

 

---

My Code

#include <stdio.h>
int n, c, C;
int a[100]={-2,}; //굳이 -2로 두지 않아도 됨
void f(int gg, int jj){ //gg는 가지, jj는 판단하는 값을 나타내는 변수
	if (gg==n-1){
	    if (jj==1) a[gg]=1; 
    	else a[gg]=0;
    	c=0; //0이 같이 있는지 판단하는 변수
		for(int i=1; i<n; i++){
			if (a[i-1]==0&&a[i]==0){
			    c++;
			}
		}
		if (c==0) C++;  //c==0이라면 0이 연달아서 나오는 경우가 없다는 뜻
		return; //탐색 종료
	}
	if (jj==1) a[gg]=1; //jj가 1이면 배열에 1 널기
	else a[gg]=0; //jj가 0이면 배열에 0 넣기
	f(gg+1, 1); //그 다음으로 뻗어가는 가지
	f(gg+1, 0); 
}
int main(){
	scanf("%d", &n);
	f(0, 1); //가지는 첫번째 가지, 1로 시작
	f(0, 0); //가지는 첫번째 가지, 0으로 시작
	printf("%d", C);
}

 
일단 바로 코드를 먼저 보여드리겠습니다. 
 

사실 혼자서 머리를 굴려봐도 dfs가 이해가 안 돼서 코드를 어떤 느낌으로 짜야 할 지 정말 막막했습니다. 예제를 찾아봐도 맨날 c++벡터를 이용하거나 파이썬을 사용하는 코드들 밖에 없어서 예시를 보고 감을 잡고 싶은데 그럴 수도 없었던 상황이었고... 그래서 결국 1시에 연락해도 안 자고 있을 것 같은 사람 1위에게 연락하여 도움을 받았습니다. (역시나 안 자고 있었음) 
 

받은 코드는 OX 투표하기?였는데요.


여기서 그나마 dfs에 대해 조금 이해를 할 수 있게 되었습니다.  (근데 아직도 완벽히 이해 못 함)
dfs는 보통 나무로 많이 비유가 되는데요. 제가 깨달은 바로 dfs를 조금 판단해보자면 dfs에서 핵심적인 부분은 현재 내가 어디를 탐색하고 있는가, 그리고 현재 내가 있는 곳의 값은 무엇인가를 기록해 두고 이를 통해 판단하는 것이라고 생각했습니다.



계획도

어려웠던 점

처음에는 다음 가지에 0을 뻗으면 그 다음번에는 0으로 가지를 뻣지 못하오록 재귀를 부르는 과정에서 조건문을 넣으려고 했습니다. 근데 코드가 정말 쓸데없이 복잡하게 짜져서 이건 아니다 싶었습니다. 그 과정에서 어떻게 진행되는지 일일이 printf를 넣어서 확인해봤으나.. 그래도 알 수 없었습니다.

그래서 저는 시간은 오래 걸리더라도 일단 조건 없이 이진수를 만들고, 그걸 추후에 비교하는 형식을 통해 해결하였습니다.

 

아래는 링크입니다
https://codeup.kr/problem.php?id=2653 

규칙에 맞는 이진수 만들기 (Small)