c언어 17505번 링고와 순열 (백준)

#include <stdio.h>
#include <stdlib.h>
long int n, k;
int cnt = 0;

void loop(long int max, long int num, int a[], int b[])
{	
	if(num == 0) {
		for(int i = 0; i<cnt; i++) printf("%d ", b[i]);
		for(int i = 0; i<n; i++) 
			if(a[i] > 0) printf("%d ", a[i]);	
		exit(0);
	}
	
	int j = 0;
	for(j = max; j>0; j--)
	{
		long int tmp = num-j;
		if(tmp >=0) {
			b[cnt++] = j+1;
			a[j] = 0;
			loop(max-1, tmp, a, b);
		}
	}
	
	if(num > 0 && j==0) {
		printf("-1");
		exit(0);
	}
}

int main(void)
{
	scanf("%ld %ld", &n, &k);
	int a[n];
	int b[n];
	
	for(int i = 0; i<n; i++) a[i] = i+1;
	loop(n-1, k, a, b);
}

 

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

17505번: 링고와 순열

 

풀이

ex) N = 5일 때 가능한 반전의 개수 0 ~ 10

1 2 3 4 5 = 0개

5 1 2 3 4 = 4개

4 1 2 3 5 = 3개

3 1 2 4 5 = 2개

2 1 3 4 5 = 1개 이므로,

0~10까지의 반전을 만들 수 있다. 그 이상은 불가능 하다.

 

1) 배열 생성

a[n] : 1~n까지를 담는 배열 생성

b[n] : 이동 시킨 수를 담는 배열

 

2) 재귀 함수, 특정 순열을 만들 수 있는 가?

(반전의 개수 - 숫자를 하나 옮겼을 때 만들어지는 반전의 개수) > 0 을 반복해서,

반전의 개수가 0이 되면 특정 순열을 만들 수 있음을 의미다.

여기서 순열에 같은수는 존재 하지 않으므로, 특정 숫자를 한 번 옮겼을 때

그 수를 b[]에 저장한 후, 더 이상 옮기지 못하게 만든다 (a[]에 있는 그 수를 0으로 만든다)

 

3) 처음 입력 받았던 반전의 개수가 0 이되면, 특정 순열을 출력 (b[] 출력 후 a[]출력)

(단 b[]에서 출력했던 것은 a[]에서 출력해서는 안됨)

역으로 처음 입력 받았던 반전의 개수가 0이 될 수 없다면 -1을 출력