8. codeup 2608 : 동아리 회장 선거 문제 해결

이번 글에서는 코드업 2608번 문제인 동아리 회장 선거 문제를 해결해 봅시다.

출처 <코드업 사이트>

문제의 내용은 다음과 같은데요 

 

다음과 같이 알고리즘을 설계해 보았습니다. 사람 수 n이 주어지면 배열에 우선 O부터 저장하기 시작합니다. O를 계속 저장하다 보면 사람 수 만큼 O가 배열에 저장되었을 것입니다. 그러면 그것이 하나의 경우의 수가 완성된 것이고 이제부터는 O의 갯수를 하나씩 줄여가며 그 자리에 X를 추가해주는 것입니다. 또 그다음은 O를 저장하고 다음은 O를 제거하고 X를 추가하고... 이러한 작업을 반복하다 보면 모든 경우의 수가 나오게 될것입니다. 

 

이러한 반복적인 작업은 재귀적으로 표현할 수 있을 것 같아 재귀함수로 표현해 보았습니다. 

#include <stdio.h>
char arr[7];  //문자열 저장 배열

void f(int a, int n){     //함수
	if(a==n){      //문자의 수가 사람수와 같아지면 출력
		for(int i=0;i<n;i++)
			printf("%c", arr[i]);
		printf("\n");
		return;    //이전 재귀로 복귀
	}
	arr[a]='O';    //O부터 추가
	f(a+1,n);
	arr[a]='X';   //그다음 X 추가
	f(a+1,n);
}

int main(){
	int n;
	scanf("%d",&n);

	f(0, n);   //배열의 0번 인덱스부터 저장
}

 f 라는 함수를 선언하였습니다. main 함수에서 0을 인자로 주면 0번 인덱스부터 O가 차곡차곡 쌓이게 됩니다. 이때에는 a+1을 인자로 전달하여 인덱스가 하나씩 증가하도록 하였습니다. 이게 사람수와 같아지면 return 함수를 사용하여 이전 재귀로 복귀하도록 하였습니다. 그러면 복귀한 인덱스에는 X가 채워지게 되고 그 후 함수를 호출하여 O,X가 채워지는 작업이 재귀적으로 실행됩니다. 

 

예를 들어 n=2일때 

O

OO -> O로 복귀

OX ->    로 복귀

XO->   X로 복귀

XX

 

이 순으로 실행되게 됩니다. 

 

 

지금 보니 n을 그냥 전역변수로 선언해도 괜찮을것 같다는 생각이 드네요.

오늘은 여기서 글을 마치겠습니다. 감사합니다.