[Baekjoon/🥈SilverⅡ] 6603: 로또

Intro

접근 방법🙋‍♀️

• ‘7 1 2 3 4 5 6 7’이 입력으로 주어지는 경우를 생각해보자.

  • 출력되는 로또 번호들은 다음의 그래프들로 나타낼 수 있다.
  • 해당 그래프를 dfs 탐색하며 모든 로또 번호들을 출력하면 문제를 해결할 수 있다.

🙋‍♀️그렇다면 해당 그래프는 어떻게 만들어지는 것일까?

• 모든 수들은 오름차순으로 주어진다.

• 우선 첫 번째로 올 수 있는 수는 해당 숫자를 포함해 총 6개의 수를 선택해야 하므로 'k - 6 + 1'번째 숫자까지만 가능하다.

• 그 다음에 오는 수도 위 방식과 마찬가지로 그 수를 포함해 그 후 수들을 선택했을 때 뽑아야하는 수를 채울 수 있는 순서의 수까지만 선택을 하면 된다.

이렇게 말로된 설명보다는 코드를 직접 보는 것이 훨 이해가 잘 될 것이다.

Algoritm👩‍💻: DFS

# 21.01.11
# 6603: 로또

from copy import deepcopy
from ntpath import join
import sys
sys.setrecursionlimit(10000)

def dfs(i, queue):
  q = deepcopy(queue)
  q.append(lst[i])
  if len(q) == 6:
    print(" ".join(q))
    return
  else:
    for j in range(i+1, k-(6-len(q))+1): # 각 위치에 올 수 있는 수들 고르기
      dfs(j, q)

while 1:
  lst = list(sys.stdin.readline().rstrip().split())
  k = int(lst[0])
  if k == 0:
    break

  lst = lst[1:]
  for i in range(0, k-5): # 첫 번째로 올 수 있는 수들 고르기
    queue = []
    dfs(i, queue)
  print("\n", end="")

✍순열, 조합, 곱집합

✍순열: Permutation

• 서로 다른 n개 중에서 r개를 골라 순서를 정해서 나열한 것
• (A, B) != (B, A)

  import itertools

  lst = [1, 2, 3]
  nPr = itertools.permutations(lst, 2)
  print(list(nPr))

• 결과: [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

✍조합: Combination

• 서로 다른 n개 중에서 r개를 골라 나열한 것
• (A, B) == (B, A)

  import itertools

  lst = [1, 2, 3]
  nCr = itertools.combinations(lst, 2)
  print(list(nCr))

• 결과: [(1, 2), (1, 3), (2, 3)]

✍곱집합: Cartesian product

• 여러 집합들에서 하나씩 뽑아 만든 조합들

  import itertools

  lst1 = [1, 2, 3]
  lst2 = ['a', 'b', 'c']
  result = itertools.product(lst1, lst2)
  print(list(result))

• 결과: [(1, ‘a’), (1, ‘b’), (1, ‘c’), (2, ‘a’), (2, ‘b’), (2, ‘c’), (3, ‘a’), (3, ‘b’), (3, ‘c’)]

Algoritm👩‍💻: combination

• 그렇다면 위에서 알아본 combination을 사용해서 문제를 해결해보자.

import itertools, sys

while 1:
  lst = list(sys.stdin.readline().rstrip().split())
  k = int(lst[0])
  if k == 0:
    break

  result = list(itertools.combinations(lst[1:], 6))
  for i in result:
    print(" ".join(i))

  print()

참고📃

• https://velog.io/@dramatic/Python-permutation-combination-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9
• https://ourcstory.tistory.com/414
• https://pacific-ocean.tistory.com/238
• https://velog.io/@dramatic/Python-permutation-combination-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9
• https://brownbears.tistory.com/453

그럼!! 이번 포스팅은 여기서!!

끝!! ~(˘▾˘~)