[백준] 6603 - 로또

1. 문제

6603번: 로또

2. 개요

독일 로또는 1부터 49개의 숫자 중 6개를 뽑는다.

로또 번호를 뽑는 방법 중 가장 유명한 방법은 미리 6이상인 k개의 수를 뽑아놓고 그 숫자들만 이용해 번호를 선택하는 것이다.

k와 수의 집합 S가 주어졌을 때, 만들 수 있는 모든 로또 번호의 수를 사전순으로 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

집합 S에서 만들 수 있는 길이 6짜리인 조합을 사전순으로 모두 출력하면 된다.

입력이 사전순으로 들어오기 때문에 어떤 수를 집합에 넣으면 그 다음숫자부터 탐색하는 방법으로 백트래킹을 구현한다.

집합의 길이가 6이 되었다면 이를 출력하는 방식을 이용하면 된다.

Python의 경우 itertools를 이용한 방법도 쓸 수 있을 듯 싶다.

3-2. Python

import sys

while True:
    nums = list(map(int, sys.stdin.readline().split()))

    if nums[0] == 0:
        break

    def bt(result, idx = 0):
        if len(result) == 6:
            print(*result)

        else:
            for i in range(idx + 1, len(nums)):
                bt(result + [nums[i]], i)

    bt([])
    print()

3-3. C#

namespace boj_6603
{
    internal class Program
    {

        static StreamReader sr;
        static StreamWriter sw;
        static int[] nums;

        static void Main(string[] args)
        {
            sr = new StreamReader(Console.OpenStandardInput());
            sw = new StreamWriter(Console.OpenStandardOutput());

            while (true)
            {
                nums = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

                if (nums.Length == 1)
                {
                    sw.Close();
                    break;
                }
                    

                BT(new List<int>(), 0);
                sw.WriteLine();
            }
        }

        static void BT(List<int> result, int idx)
        {
            if (result.Count == 6)
            {
                foreach(int num in result)
                    sw.Write($"{num} ");

                sw.WriteLine();
            }

            else
            {
                for (int i = idx + 1; i < nums.Length; i++)
                {
                    BT(result.Append(nums[i]).ToList(), i);
                }
            }
        }
    }
}