[백트래킹 / python] 백준 6603. 로또

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

6603번: 로또

 

문제 해석

위 문제는 조합으로도 쉽게 풀 수 있는 문제이지만, 백트래킹으로도 풀 수 있을 것 같아 백트래킹으로 풀어보려고 한다.

 

조합

이 풀이는 itertools 라이브러리의 조합을 이용하면 된다. 단순히 주어진 리스트 값에서 6개의 숫자를 뽑아주면 되는 문제다. 입력의 수가 주어지지 않아 혹시 몰라서 EOF처럼 try/except를 걸어주었다.

# 첫 번째 풀이 : 조합 이용
import sys
input = sys.stdin.readline
from itertools import combinations as cb


while True:
    try:
        li = list(input().split())
        if li[0] == '0': break

        k = int(li[0])
        arr = li[1:]
        # print(k, arr)
        # print(type(arr))
        for i in cb(arr, 6):
            print(*i)
        print()
    except Exception:
        print("e")
        break

 

백트래킹

백트래킹으로 풀기 위해서 가지를 쳐내야 하는 점은, 오름차순으로 정리되어야 하며, 숫자가 중복이 되면 안된다. 우선 오름차순이 되어야 하므로 is_promising에서 정답 배열의 top에 있는 요소와 대소비교를 하였으며, 재귀 함수의 호출 루프문의 시작값을 depth로 설정함으로써 중복을 피하고자 했다.

# 두 번째 풀이 : dfs & back-tracking 이용
import sys
input = sys.stdin.readline

def go(depth, ans):
    if len(ans) == 6:
        print(*ans)
        return
    else:
        for i in range(depth, len(li)):
            if is_promising(i):
                ans.append(li[i])
                go(depth+1, ans)
                ans.pop()
def is_promising(i):
    if len(ans) == 0:
        return True
    elif li[i] > ans[-1]:
        return True
    return False

while True:
    li = list(map(int, input().split()))
    if li[0] == 0: break
    li = li[1:]
    ans = list()

    go(0, ans)
    print()

 

메모:

주어진 수열이 중복된 숫자가 없다면, 중복을 피하기 위한 방법으로 아래와 같이 루프문에 depth를 추가할 수 있다.

for i in range(depth, len(list))