백준 6603번 문제 ( 로또 )

문제 출처 : https://www.acmicpc.net/problem/6603

6603번: 로또

이번 문제는 전체 경우의 수를 출력하는 문제이지만 사전순으로 출력을 해야 한다.

그래서 DFS 기법과 백트래킹 기법을 이용하여서 문제를 해결하였다.

로또는 6자리의 수를 가지고 하는 것이기 때문에 배열을 선언한 후 그 배열의 값을 바꾸어가면서 답을 출력하였다. 

1 2 3 4 5 6 7 와 같은 예제에서 맨 처음에 1 2 3 4 5 6 을 배열에 넣게 된 뒤 그 이후 6이 7로 교체되고 출력한다. 

그 이후 그 다음 큰 수인 5가 6으로 교체되고 반복하는 형식으로 답을 출력하게 된다. 

백 트래킹과 DFS 기법을 사용해보았는데 아직도 많이 어렵다. 

더욱 공부를 해야겠다는 생각이 들게 되었다.

아래는 해당 문제를 해결한 소스이다. 

 

#include<stdio.h>
#pragma warning(disable:4996)
int lotto[7];
int arr[14];
void find(int start, int depth, int N)
{
    if (depth == 6) {                   
        for (int i = 0; i < 6; i++) {
            printf("%d ", lotto[i]);
        }
        printf("\n");
        return;
    }
    for (int i = start; i < N; i++) {   
        lotto[depth] = arr[i];      
        find(i + 1, depth + 1, N);
    }
}
int main()
{
    while (1)
    {
        int N;
        scanf("%d", &N);
        if (N == 0)
            return 0;
        else
        {
            for (int i = 0; i < N; i++)
                scanf("%d", &arr[i]);
            find(0,0,N);
            printf("\n");
        }
    }
}