[jungol] Beginner_Coder / 재귀 / 2817 / 로또(Lotto) / python

2817 : 로또(Lotto)

제한시간1000 ms    메모리제한128 MB    해결횟수715 회    시도횟수1135 회   

문제

로또에서는 {1, 2, 3, ... , 48, 49} 번호 중에 6개를 선택해야 한다.

로또 번호를 선택하는 데는 여러 가지 전략이 있겠지만 우리는 49개의 수 중에서 K( 6 < K < 13)개가 이미 선택되어 있다고 가정하고 

이 선택된 수들로 만들 수 있는 로또 번호를 만들어 보기로 한다.

 

예를 들어 K = 8이고 선택된 수들의 집합 S = {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], ... [3,5,8,13,21,34]. 로 28개가 있다.

 

수의 개수 K와 K개의 수가 주어질 때 가능한 로또 번호를 출력하는 프로그램을 작성하시오.

 

입력형식

하나의 행에 정수가 주어진다. 첫 수는 수의 개수 K(6 < K <13) 이다.

이어서 공백으로 구분하여 K개의 자연수 Si( 1≤ Si ≤ 49)가 오름차순으로 정렬되어 주어진다.

 

출력형식

주어진 K개의 수로 만들 수 있는 가능한 로또 번호를 행으로 구분하여 출력한다.

각 행의 수들과, 행으로 구분된 로또 번호들은 오름차순으로 출력되어야 한다.

 

입력

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

 

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2082&sca=2080 

JUNGOL

 

🤔문제풀이

1. 로또니깐 r이 6으로 고정되어있는 조합문제이다.

2. 재귀를 이용해서 nC6 조합을 구현해서 풀면된다!

 

답은 k이 6일 때만 뽑으면 되는데 내부에선 아래와 같은 로직으로 돌아간다.

어느정도 이해는 되는데 솔직히 설명해봐라 하면 잘 못하겠다. 비슷한 문제를 자주 풀어보면서 익혀야 될 것 같다.