사이트 #문제: 문제유형 / 난이도

문제 링크 : https://www.acmicpc.net/problem/6603

[BOJ]#6603로또/Backtracking/실버2

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

유형 : Backtracking

주어진 K개의 자연수 집합에서 6개를 뽑는 모든 조합의 경우의 수를 찾는 문제이다.

🚩 FLOW

코드를 풀이할 때 적었던 플로우가 있나요?

1. 입력 변수 정의하기
   • 입력 : K . {K개의 숫자 조합}
2. backtracking 함수 정의하기

   • 매개 변수

     level : 출력 조합 result에 현재 선택한 원소가 들어갈 위치

     idx : 현재 level 에서 사용 가능한 원소들의 범위 인덱스 idx ~ -1

     → 조합의 경우 , 이전 level(level-1)선택한 원소의 위치 i 보다 뒤에 있는 숫자 조합들 선택하면 된다.

   • 종료 조건

     level == 6 # 출력 배열 result의 원소가 6개를 충족할 경우

   • 함수 정의

     1. level == 6 이면 함수 종료

     2. idx ~ k 범위의 숫자를 출력 변수 result[level] 에 대입

     3. level+1 으로 이동 ,탐색 범위를 idx → i+1 로 이동

        *조합은 현 level에서 선택한 i보다 작은 숫자는 탐색 할 필요 없음

🚩제출한 코드

"""
[BOJ]6603로또/실버2
<https://www.acmicpc.net/problem/6603>

-주어진 K개(k>6) 숫자에 6개 뽑아 대해 중복x 한 조합의 경우의 수 찾기
->중복 x , 순서 상관x
- 해당 모든 경우의 수는 사전 순으로 출력
- 입력 : K , {해당하는 숫자의 조합}
"""

import sys
input = sys.stdin.readline
# 1. 입력 변수 및 출력 형식에 맞춰 설정하기
while True :
  set_s = list(map(int, input().split()))
  answer = []
  if len(set_s) < 2 : 
    break 
  k= set_s.pop(0)
  #2. 유효성 검사 is_valid 정의
  # check = [True]*len(set_s[1:])
  result = [0]*6 # 출력 리스트
  #3. 백트래킹 함수 정의
  def conbination(level ,idx ): 
    #종료 조건
    if level == 6 : 
      answer.append(result.copy())
      # print(result)
      return 
    # 동작 과정
    for i in range(idx,k):
      result[level] = set_s[i]
      conbination(level+1 ,i+1) # 조합은 idx 보다 작은 i는 탐색 할 필요 없음
      result[level] = 0 
  conbination(0,0)
  # print(answer)
  # 3. 출력 형식 맞추기
  for a in answer: 
    print(" ".join(map(str,a)))
  print("")