[class2]백준 6603번(로또) - 코테공부 24일차(2025.02.15)

문제유형

조합

풀이 방법 도출 과정

1. 조합 알고리즘을 구현하는 것이 목표

2. 이 방법대로 구현해보도록 하겠다.

시간 복잡도

• 시간 복잡도는 최악의 경우 k가 13이므로 13C6의 결과는 O(1)이다.

코드 및 간단설명

재귀함수를 사용하여 문제를 풀었다. 이건 간단히 조합을 구현하면 되는 문제였다. 

first_case = True  # 첫 번째 테스트 케이스 여부 체크

while True:
    lst = list(map(int, input().split()))
    N = lst.pop(0)  # 첫 번째 값을 N으로 설정
    
    if N == 0:  # 종료 조건
        break

    if not first_case:
        print()  # 테스트 케이스 구분을 위해 빈 줄 출력
    first_case = False

    R = 6
    choose = []

    def combination(index, level):
        if level == R:
            print(*choose)  # 리스트를 공백으로 구분하여 출력
            return

        for i in range(index, N):
            choose.append(lst[i])
            combination(i + 1, level + 1)
            choose.pop()

    combination(0, 0)

다른 풀이

1) 파이썬 라이브러리 사용

이 방법이 더욱 더 쉬운 방법으로 파이썬 라이브러리를 사용하는 방법이 있다. 이것은 많은 사람들이 사용하는 방법이다. 

import itertools

first_case = True

while True:
    data = list(map(int, input().split()))
    N = data[0]
    if N == 0:
        break
    if not first_case:
        print()
    first_case = False

    numbers = data[1:]
    
    for comb in itertools.combinations(numbers, 6):
        print(*comb)