/ 알고리즘

로또 번호

알고리즘 for 문 다중 반복문 로또 번호 배열
https://4am.kr/-eb-a1-9c-eb-98-90--eb-b2-88-ed-98-b8/

프로그램 명: lotto

제한시간: 1 초
독일 로또에서는 1 에서 49 까지의 수 중 6 개를 고른다.

당첨되는 확률이 높아지는 것은 아니지만 로또의 일반적인 전략은 원소의 개수가 K 인 전체 집합 S 에서 6 개의 원소를 가지는 모든 부분집합 중에서 하나를 고르는 것이다.

예를 들어 , k = 8 이고 S = {1,2,3,5,8,13,21,34} 인 경우 6 개의 원소를 가지는 부분집합은 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].

수 k 와 집합 S 가 주어질 때 가능한 모든 경우를 모두 출력하는 것이 문제이다.

입력

k 는 6 이상 13 이하의 정수이다. 다음으로 k 개의 수 S 가 주어진다. S 는 오름차순 순으로 입력된다.

출력

사전식으로 먼저 나오는 순으로 출력한다.

입출력 예

입력 7 1 2 3 4 5 6 7 

출력 1 2 3 4 5 6 1 2 3 4 5 7 1 2 3 4 6 7 1 2 3 5 6 7 1 2 4 5 6 7 1 3 4 5 6 7 2 3 4 5 6 7 입력 8 1 2 3 5 8 13 21 34 출력 1 2 3 5 8 13 1 2 3 5 8 21 1 2 3 5 8 34 1 2 3 5 13 21 1 2 3 5 13 34 1 2 3 5 21 34 1 2 3 8 13 21 1 2 3 8 13 34 1 2 3 8 21 34 1 2 3 13 21 34 1 2 5 8 13 21 1 2 5 8 13 34 1 2 5 8 21 34 1 2 5 13 21 34 1 2 8 13 21 34 1 3 5 8 13 21 1 3 5 8 13 34 1 3 5 8 21 34 1 3 5 13 21 34 1 3 8 13 21 34 1 5 8 13 21 34 2 3 5 8 13 21 2 3 5 8 13 34 2 3 5 8 21 34 2 3 5 13 21 34 2 3 8 13 21 34 2 5 8 13 21 34 3 5 8 13 21 34

출처: Ulm Local 1996

/* 힌트(by dovelet) 
1 2 3 4 5 에서 3 개를 중복없이 고르는 경우 
i , j , k 는 
i j k ------ 
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
3 4 5 
이렇게 발생하기 위해서 반복문은 다음과 같이 사용하면 됩니다.
==> 부분집합이 3개 이므로 반복문도 3개 
==> 숫자들의 갯수 기준으로 -1씩(안쪽 반복문 기준으로) 
for( i = 1 ; i <= 3 ; i++){ 
for( j = i + 1 ; j <= 4 ; 
j++){ 
for( k = j + 1 ; k <= 5 ; k++){ 
... 
} 
}
 } 

아래의 경우 숫자는 주어진 n 기준으로 6개의 숫자를 받아야 하므로 6개의 for문과 안쪽 반복문 기준으로 -5까지 됨 
*/

#include <iostream>
using namespace std;
int main()
{
    int n;
    int ltt[49] = {
        0,
    };
    cin >> n;
    //입력
    for (int i = 0; i < n; i++)
        cin >> ltt[i];
    //for문 6개
    for (int a = 0; a < n - 5; a++)
        for (int b = a + 1; b < n - 4; b++)
            for (int c = b + 1; c < n - 3; c++)
                for (int d = c + 1; d < n - 2; d++)
                    for (int e = d + 1; e < n - 1; e++)
                        for (int f = e + 1; f < n; f++)
                            cout << " " << ltt[a] << " " << ltt[b] << " " << ltt[c] << " " << ltt[d] << " " << ltt[e] << " " << ltt[f] << endl;
    return 0;
}