U E D R , A S I H C RSS

자알하자/2015.03.12/코드

김정민 : MORSE

#include <stdio.h>
#include <string.h>

//콤비네이션 함수를 "동적 계획법"으로 짜볼까요
long com[201][101];
long combi(int n, int r){
	if(com[n][r] != -1 ) return com[n][r];
	else if(n == 0) return 0;
	else if(r== n || r == 0){ com[n][r] = 1; return 1; }
	else{ com[n][r] = combi(n-1,r-1) + combi(n-1,r); return com[n][r];}
}

void make_temp_result(int m_temp, int k_temp);
void make_result();

char result[201] = { 0, };	//null을 위한 한칸
char temp_result[201] = { 0, }; //조합이 너무 커지는 경우가 발생할 경우 앞 부분이 '-'가 연속해서 나오므로 처음 나온 'o'부터의 문자열을 '거꾸로 순서로'!! 여기에 저장
int n,m,k;
int num_of_maketempresult;	//함수 실행 횟수

int main(){
	for(int i=0;i<201;i++){for(int j=0;j<101;j++) com[i][j] = -1;}
	int tc;
	scanf("%d",&tc);
	for(int i=0;i<tc;i++){
		//memset으로 초기화!!를 해줘야되용
		memset(result,0,m+n);
		memset(temp_result,0,m+n);
		num_of_maketempresult = 0;

		scanf("%d%d%d", &n,&m,&k);
		make_result();
		printf("%s\n",result);
	}

	return 0;
}

void make_result(){
	make_temp_result(m,k);
	for(int i=0;i<m+n - strlen(temp_result);i++) result[i] = 45;
	for(int i=0;i<strlen(temp_result);i++) result[m+n-1-i] = temp_result[i];
}


void make_temp_result(int m_temp, int k_temp){
	int i;
	for(i=m_temp;k_temp>combi(i,m_temp);i++);
	temp_result[i-1] = 111;
	if(num_of_maketempresult == 0){	for(int j=0;j<i-1;j++) temp_result[j] = 45; }	//해당 줄은 앞을 전부 '-'로 만들어줍니다!
	num_of_maketempresult++;
	if(num_of_maketempresult < m) make_temp_result(m_temp-1, k_temp - combi(i-1,m_temp));
}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:30:41
Processing time 0.0127 sec