c언어 15663번 N과 M (10) (백준)

https://www.acmicpc.net/problem/15664

15664번: N과 M (10)

 

 

 

 

#include <stdio.h>

int sort[10] = {0};
int tmp[10] = {0};
int exist[10] = {0}; //같은 것의 중복을 방지
int n = 0;
int m = 0;

void loop(int k, int x) //int x은 비내림차순을 위한 것
{
	if(k==m)
	{
	for(int i = 0; i<m; i++) printf("%d ", tmp[i]);
		
		printf("\n");
		return;
	}
	
	int before = 0; //정렬 내 중복을 방지
	for(int i = x; i<n; i++)
	{
		
		if(exist[i] == 0 && before != sort[i])
		{
			before = sort[i];
			exist[i] = 1;
			x = i;
			tmp[k] = sort[i];
			loop(k+1, x);
			x = x-i;
			exist[i] = 0;
			tmp[k] = 0;
		}
		if(k==0) x++;
	}
}

int main(void)
{
	scanf("%d%d", &n, &m);
	for(int i = 0; i<n; i++) scanf("%d", &sort[i]);
	
	int gap = n/2;
	int key = 0;
	int i, j;
	
	while(1==1)
	{
		if(gap%2==0) gap++;
		for(i = gap; i<n; i++)
		{
			key = sort[i];
			for(j=i-gap; j>=0; j=j-gap)
			{
				if(key<sort[j]) sort[j+gap] = sort[j];
				else break;
			}
			sort[j+gap] = key;
		}
		if(gap==1) break;
		gap /= 2;
	}
	
	loop(0, 0);
	return 0;
}

 

N-M 풀이 (?)

 

조건 :  중복되는 수열을 여러 번 출력하면 안되며...

-> 위 코드의 int before처럼 이전 값을 저장하여, 정렬된 수열에 같은 값들이 있어 중복되는 수열을 출력하는 것을 방지한다.

 

조건 : 수열은 사전 순으로 증가하는 순서로 출력해야 한다... (비 내림차순)

-> 위 코드의 int x처럼 재귀 함수가 돌아갈수록 x값은 커지면서, 조합처럼, 작은 값이 뒤에 나오지 못하게 한다.

 

조건 : 같은 수를 여러 번 골라서는 안된다.

-> 위 코드의 int exist[10] = {0};처럼 재귀하는 동안 이미 했던 건 exist[i]의 값을 바꿔주어, 같은 수를 여러 번 고르는 것을 방지한다. 즉, int exist 같은 장치를 없에면 같은 수를 여러번 고를 수 있는 수열이 된다.

 

 

N-M (10) 풀이

 

조건 (1) : 중복되는 수열을 여러 번 출력하면 안 되며,

조건 (2) : 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 

ex)

{ input : 4 2

           9 7 9 1

 

 output : 1 7

            1 9

            7 9

            9 9

 이므로 비 내림차순이라는 뜻이다.

 또한 1 1, 7 7이 없으므로 같은 수를 여러 번 고르지도 않는다.

 

}

 

조건 (1)은 각 재귀 함수마다, 이전 값을 저장한 뒤 비교해주는 변수를, 그리고 같은 수를 여러 번 고르지 않으므로, exist[10] 같은 장치를 

조건 (2)은 int x 같이 재귀를 여러번 할수록 점점 증가하여, 큰 수 뒤에 작은 수가 나오는 불상사를 막으면 된다.