[Algorithm] 6603. 로또

6603: 로또(백트래킹)

https://www.acmicpc.net/problem/6603

• 문제 티어 : S2
• 풀이 여부 : Failed
• 소요 시간 : 34:41

정답 코드

정답코드 1 : 백트래킹 적용

import sys
input = sys.stdin.readline

def backtrack(arr, index, curr):
  if len(curr) == 6:
    print(*sorted(curr))
    return

  for next_index in range(index, len(arr)):
    curr.append(arr[next_index])
    backtrack(arr, next_index + 1, curr)
    curr.pop()

while True:
  input_line = input().rstrip()
  if input_line == '0':
    break

  cmd_int = list(map(int, input_line.split()))
  K, arr = cmd_int[0], cmd_int[1:]
  backtrack(arr, 0, [])
  print()

정답코드 2 : itertools 사용

import sys
from itertools import combinations

input = sys.stdin.readline

while True:
  arr = list(map(int, input().split()))
  if len(arr) == 1 and arr[0] == 0:
    break
  else:
    k = arr[0]
    S = arr[1:]
    candidate = list(sorted(combinations(S, 6)))
    for candi in candidate:
      print(*candi)
    print()

접근 방식

N과 M 문제에서 연습했던 백트래킹 풀이 방식과 거의 동일하다.

• N과 M (5)

# 03:30 Solved
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
arr = sorted(list(map(int, input().rstrip().split())))
ans = []

def backtrack(curr):
  if len(curr) == M:
    ans.append(curr[:])
    return
    
  for num in arr:
    if num not in curr:
      curr.append(num)
      backtrack(curr)
      curr.pop()

backtrack([])

for i in range(len(ans)):
  print(*ans[i])

위 코드와 동일하게 처음에는 backtrack 함수에 curr만 넘겨주는 방식으로 구현했다.

import sys

def backtrack(arr, curr):
  if len(curr) == 6:
    print(*curr)
    return
    
  for num in arr:
    if num not in curr:
      curr.append(num)
      backtrack(arr, curr)
      curr.pop()

while True:
  input_line = input().rstrip()
  if input_line == '0':
    break

  cmd_int = list(map(int, input_line.split()))
  K, arr = cmd_int[0], cmd_int[1:]
  backtrack(arr, [])
  print()

하지만 이렇게 코드를 작성했더니 출력초과가 나왔다.
수정해준 코드에서는 backtrack 함수의 인자로 arr, index, curr을 받아, index 인자를 추가해 이미 고려된 요소를 건너뛰고 중복 없이 모든 가능한 조합을 탐색하고자 했다.

def backtrack(arr, index, curr):
  if len(curr) == 6:
    print(*sorted(curr))
    return

  for next_index in range(index, len(arr)):
    curr.append(arr[next_index])
    backtrack(arr, next_index + 1, curr)
    curr.pop()

배운점 또는 느낀점

사실 파이썬에서는 itertools의 combinations를 사용해서 너무 쉽게 구현할 수 있지만 백트래킹 연습 중이니 풀이방법을 익히고자 직접 구현했다.
백트래킹은 참 어렵다..!! 열심히 연습해야지!!