590 : 함수3 - 자가진단4

10 이하의 자연수 N을 입력받아 주사위를 N번 던져서 나올 수 있는 모든 경우를 출력하되 중복되는 경우에는 앞에서부터 작은 순으로 1개만 출력하는 프로그램을 작성하시오.

 

3을 입력했을 때,

1 1 1

1 1 2

...

1 1 6

1 2 2

1 2 3

...

5 6 6

6 6 6

 

HInt !

"1 1 2", "1 2 1", "2 1 1"은 모두 1이 두 번 2가 한 번 나온 경우이므로 중복이다. 이러한 경우 앞에서부터 작은순으로"1 1 2"한 가지만 출력해야 한다. 현재의 레벨(arr[i])에 담을 값을 1부터가 아니라 이전 레벨에 담겨있는 값(arr[level-1])부터로 정하면 된다. 이 경우 level[0]에는 어떤 값을 넣어야 할지 잘 생각해 보자.

 

#include<stdio.h>
int n,a[101];

void output(){
	int i;
	for(i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	printf("\n");
}

void dice(int level){
	int i;
	if(level > n){
		output();
		return;
	}
	
	for (i=a[level-1];i<=6;i++){
		a[level]=i;
		dice(level+1);
	}
}

int main(){
	scanf("%d",&n);
	a[0]=1;
	
	dice(1);
	return 0;
}

 

문제를 이해할 수 없어서 다른 사람들이 만들어놓은 코드를 먼저 찾아봤다.

코드를 읽으면서 원리를 파헤쳐보자.

 

 

int n,a[101];

가장 첫 줄에 미리 변수 선언을 해준다.

 

int main(){
	scanf("%d",&n);
	a[0]=1;
	
	dice(1);
	return 0;
}

 

main 함수는 이와 같다.

주사위를 몇 번 돌릴지 정하는 변수 n을 입력받고

a[0]를 1로 초기화 해준다. (주사위는 1부터 시작하기 때문)

함수 dice를 호출한다.

 

void dice(int level){
	int i;
	if(level > n){
		output();
		return;
	}
	
	for (i=a[level-1];i<=6;i++){
		a[level]=i;
		dice(level+1);
	}
}

 

입력받은 숫자인 n을 3으로 가정했을 때를 먼저 살펴보자

경우의 수는 6^3 = 216가지의 수가 나와야 하지만 중복되는 경우는 제외해야 한다.

 

dice(1)을 호출했으므로 현재 level은 1

if문은 성립되지 않기 때문에 for문으로 넘어간다.

 

for문은 level이 1일 때, (i=a[0]; i<=6; i++)이 되고

a[1]=i 에서 i=a[0]인데 main  함수에서 a[0]=1;로 정했으므로

a[1]=1이 된다.

 

밑으로 내려오면 dice(level+1)  ->  dice(2)

dice(2)를 호출하면 위와 같은 방법을 통해

a[2]=1이 나오고 dice(3)을 호출하면

a[3]또한 1이 나온다.

 

지금까지의 과정은 경우의 수 1 1 1을 구하기 위한 한 번의 반복이었다.

각 for문을 보면 6번씩 반복하므로

a[1] - a[2] - a[3]=1, a[3]=2, a[3]=3 ... a[3]=6

이렇게 1 1 1, 1 1 2, 1 1 3 ... 1 1 6과 같이 구해질 수 있다.

for문의 반복으로 a[1]이 1~6, a[2]도 1~6, a[3]도 1~6이 나오기 때문에 경우의 수는 각 각 6개씩 곱해 216가지가 나와야 하는데,

여기서 중요한 점은 Hint ! 에서 알려주었듯이 i = a[level-1]으로 지정해서 중복된 숫자는 나오지 않게 해야 한다.

 

숫자로 이해하자면,

1 1 1, 1 1 2 ... 1 1 6  다음은 1 2 1이 와야 하지만, 1 2 1은 앞서 나온 1 1 2와 숫자가 중복되기 때문에

1 2 2 부터 세야 한다. 즉, a[3]이 2부터 나와야 하는 것이다. a[level-1]을 이용하면 바로 전 원소부터 시작할 수 있다. 

1 2 2 를 구성하기 위해선 a[1] = 1, a[2] =2, a[3] = 2 이어야 한다.

level이 3일 때, i = a[level-1]은 i = a[2]부터 시작한다는 것이고, a[2]은 2기 때문에 a[3] = 2가 나올 수 있게된다.

 

 

int i;
	if(level > n){
		output();
		return;
	}
	

 

level 이 4가 되면 입력받은 숫자인 3보다 크기 때문에 output 함수를 호출하고 종료하게 된다.

 

void output(){
	int i;
	for(i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	printf("\n");
}

 

output함수는 여태까지 만든 경우의 수를 출력하는 함수이다.

이 함수들을 모두 합치면 코드가 완성된다.

 

#include<stdio.h>
int n,a[101];

void output(){
	int i;
	for(i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	printf("\n");
}

void dice(int level){
	int i;
	if(level > n){
		output();
		return;
	}
	
	for (i=a[level-1];i<=6;i++){
		a[level]=i;
		dice(level+1);
	}
}

int main(){
	scanf("%d",&n);
	a[0]=1;
	
	dice(1);
	return 0;
}

 

 

사실 어떻게 돌아가는 원리인지는 이해를 했지만 어째서 a라는 배열에 111, 112 이런식으로 저장이 될 수 있는건지는 잘 모르겠다 ...;;  혹시라도 아시는 분 댓글 달아주시면 감사하겠습니다 ..ㅠ

 

 

출처 : www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=227&sca=10d0