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

 

 

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

15663번: N과 M (9)

 

 

 

#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) //백트래킹
{
	if(k==m) //출력
	{
	for(int i = 0; i<m; i++) printf("%d ", tmp[i]);
		
		printf("\n");
		return;
	}
	
	int before = 0; 이전의 것을 담는 변수
	for(int i = 0; i<n; i++)
	{
		//이미 사용했어도, 이전 것과 같아서도 안 됨
		if(exist[i] == 0 && before != sort[i])
		{
			before = sort[i]; //이전 것에 지금 것을 넣어줌
			exist[i] = 1;
			tmp[k] = sort[i];
			loop(k+1);
			exist[i] = 0;
			tmp[k] = 0;
		}
	}
}

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) //shell 정렬
	{
		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); //백트래킹
	return 0;
}

 

 

풀이 : 순열에서 중복된 것만을 빼준다.

 

1. 반드시 어떠한 정렬 방식을 사용하여 오름차순으로 정렬한다. (위 코드는 shell 정렬 이용)

 

2. 백트래킹을 한다. 이 과정에서 중복되는 것은 제거(?)해야한다.

 

 

ex) 중복이 남아있는 상태로 출력

 

 

 

#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) //그냥 순열 출력
{
	if(k==m)
	{
	for(int i = 0; i<m; i++) printf("%d ", tmp[i]);
	printf("\n");
	return;
	}
	
	//int before = 0; before 변수가 없다!
	for(int i = 0; i<n; i++)
	{
		
		if(exist[i] == 0 && before != sort[i])
		{
			//before = sort[i]; //before 변수가 없다!
			exist[i] = 1;
			tmp[k] = sort[i];
			loop(k+1);
			exist[i] = 0;
			tmp[k] = 0;
		}
	}
}

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);
	return 0;
}

두 번째 코드에 n = 4, m = 2   9 7 9 1 로 입력을 하면

 

 

순열

 

이렇게 중복되서 나온다. (중복되는 것은 빨간 글씨에, 검은 배경,   중복되는 것 바로 앞에서 중복되는 것과 같이 가지는 수를 노란색 배경으로 표시)

 

1 7  |

1 9  |------ loop(0)에서 i = 0 일때, loop(1)

1 9  |

7 1  |

7 9  |------ loop(0)에서 i = 1 일때, loop(1)

7 9  |

9 1  |

9 7  |------ loop(0)에서 i = 2 일때, loop(1)

9 9  |

9 1  |

9 7  |------ loop(0)에서 i = 3 일때, loop(1)

9 9  |

 

 

위의 출력 결과를 보면, 이전에 나왔던 것과 같은 값을 다시 출력했기에 중복이 발생한다.

그러므로, 이전의 결과를 저장 해 놓고, 같다면, 바로 무시해버리면, 중복을 피할 수 있게 된다.

 

이전의 것을 담는 값을 여기선 before로 이름지었다.

 

loop(0) 에서의 before값은 

i = 0 일 때 loop(1)을 다 돈 후 : before = 1

i = 1 일 때 loop(1)을 다 돈 후 : before = 7

i = 2 일 때 loop(1)을 다 돈 후 : before = 9

i = 3 일 때 loop(1)을 다 돈 후 : before = 9

 

여기서 loop(0) i = 3 일 때 before이 9 이므로, 위에선 출력된 (9 1), (9 7), (9 9)는 출력되지 않는다.

 

loop(0) i = 0에서 loop(1)에서의 before값은

for 들어오기 전 : before = 0;

i = 0 일 때 if()지나친 후 : before = 0

i = 1 일 때 if()지나친 후 : before = 7

i = 2 일 때 if()지나친 후 : before = 9

i = 3 일 때 if()지나친 후 : before = 9

 

여기서 i = 2 일 때 if()지나친 후 : before = 9 이므로, i=3 일 땐 if조건이 false가 되어, (1 9)는 출력 되지 않는다.

 

---

 

이렇게 이전값을 미리 저장 해 놓으면, 중복을 피할 수 있게 된다!

 

 

ex) 첫번째 코드에 n = 4, m = 2, 9 7 9 1을 입력 했을때

 

 

결과!

중복이 사라졌다.