[BaekJoon] 백준 6603번 로또

[BaekJoon] 백준 6603번 문제이름

 

문제: www.acmicpc.net/problem/6603

 

내코드

 

• 이 문제는 백트래킹으로 풀었다.
• 주어진 숫자들에서 6개의 숫자를 선택해서 사전순으로 나열하고 출력하면 된다
• out 변수에 선택된 6개의 숫자를 차곡차곡 넣어준다.
• visited 리스트에 해당 순서의 숫자가 선택되었는지, 안되었는지 true, false로 기록해준다.
• dfs와 비슷한 방식이다. out[0]을 1이라고 선택하면, out[1]을 2로 선택한 경우를 쭉 보고, out[1]을 3으로 선택한 경우를 쭉 확인하는 방식으로 간다. 각각의 경우를 확인하면 pop을 해서 다음 경우를 확인하게 된다.
• out의 길이가 6이 되면 출력을 해준다.

 

# BaekJoon 6603.py 로또

def solve():
    if len(out) == 6:  # 길이가 6인 리스트가 완성되었다면
        print(' '.join(map(str, out)))  # 출력
        return
    for i in range(length):  # 1-n까지 수를 돌아가며
        if visited[i]: # 이미 사용한 값이면 pass
            continue
        if len(out) != 0 and out[-1] > li[i]: # 선택된 숫자들 중 가장 마지막 숫자가 현재 선택 예정인 숫자보다 크면 사전순이 아니니까 pass
            continue
        out.append(li[i])  # 사용한 것 리스트에 기록
        visited[i] = True
        solve()  # 리스트의 다음 수 정하러 들어감
        out.pop()  # k번째 수를 i로 정한 경우를 모두 확인했으므로 k번째 수를 pop하기(다음 수를 k번째에 집어넣기 위해)
        visited[i] = False


inputLi = list(map(int, input().split()))
if inputLi[0] == 0:
    exit()
li = inputLi[1:]
length = len(li)
out = [] # 선택한 숫자들 저장 위해
visited = [False] * length # 사용한 것 기록하기 위해
while inputLi[0] != 0:
    solve()
    inputLi = list(map(int, input().split())) # 다음 test case 받기
    li = inputLi[1:]
    length = len(li)
    visited = [False] * length
    out = []
    print()