[백준 - C#] 6603번 로또

문제링크

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

6603번: 로또

 

문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

조건

시간제한 : 1초
메모리 제한 : 128 MB

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스는 한 줄로 이루어져 있다.
첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다.
S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다. 

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.
각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

 

문제정리

1. 로또는 49개의 숫자 중 6개를 고릅니다.
2. k개의 수를 골라 집합 S를 만듭니다.
3. 집합 S에서 6개를 고르는 모든 경우의 수를 출력해야 합니다.

이번 문제의 경우 k개의 집합 S에서 6개를 선택 할 때 모든 경의 수를 출력 해야 하는 문제입니다.

저의 경우 DFS 전체 탐색을 이용하였지만 그와 비슷한 백트래킹 방식? 을 사용하였습니다.

DFS의 경우 모든 노드를 방문하여 탐색하지만 백트래킹의 경우 불필요한 탐색은 하지 않고 이전으로 돌아가 다른 노드를 탐색하는 방법입니다. 

 

코드를 보면 함수 DFS에서 count의 값이 6이란 소리는 6개의 로또가 다 모였기 때문에 출력 해주었고,

그 아래 반복문에서 숫자 6개의 모든 조합들을 탐색합니다

 

예를 들어 i = 5, count = 5 일 때 DFS를 탐색하면 count = 6 이 되고 123456을 출력 후 i = 6으로 시작되어 

lotto[5] = S[6] 이 되어 123457 이 되어 뒷자리부터 변경되는 것을 확인해 볼 수 있습니다.

 

C# 코드

static void Main(string[] args)
{
    // 6603
    StreamWriter writer = new StreamWriter(OpenStandardOutput());
    StreamReader reader = new StreamReader(OpenStandardInput());
 
    int[] lotto = new int[6];
    int k;
    int[] S;
 
    while (true)
    {
        string[] input = reader.ReadLine().Split();
        k = int.Parse(input[0]);
        S = new int[k];
 
        if (k == 0)
            break;
 
        for (int i = 0; i < k; i++)
        {
            // 집합 S 변환
            S[i] = int.Parse(input[i + 1]);
        }
 
        DFS(0, 0);
 
        writer.WriteLine();
    }
 
    writer.Close();
    reader.Close();
 
    void DFS(int start, int count)
    {
        if (count == 6) // 로또 6개가 다 채워졌을 때
        {
            for (int i = 0; i < 6; i++)
            {
                writer.Write($"{lotto[i]} ");
            }
            writer.WriteLine();
            return;
        }
 
        for (int i = start; i < k; i++) // 입력 받은 번호를 전부 탐색
        {
            lotto[count] = (S[i]); // 1개부터 6개까지 집합 S에서 로또 번호를 입력
            DFS(i + 1, count + 1); // 다음 번호를 입력하는 재귀함수
        }
    }
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.