[백준알고리즘/6603번/파이썬] 로또

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

6603번: 로또

 

문제: 임의의 수열이 주어졌을 때, 6개의 수를 뽑을 수 있는 경우의 수를 구하는 문제

 

풀이 방법: 백트래킹

 

풀이 코드:

import sys

def backTracking(idx):
    if len(case) == 6:
        for i in range(6):
            print(case[i],end=' ')
        print()
        return

    for i in range(idx,array[0]+1):
        if len(case) > 0:
            if case[-1] >= array[i]:
                continue
        case.append(array[i])
        backTracking(idx+1)
        case.pop()
    return

while True:
    array = list(map(int,sys.stdin.readline().rstrip().split(' ')))
    if not array[0]:
        break
    case = []
    backTracking(1)
    print()

 

풀이 설명:

풀이에 핵심이 되는 backTracking 함수를 설명하고 가겠습니다.

def backTracking(idx):
    if len(case) == 6:
        for i in range(6):
            print(case[i],end=' ')
        print()
        return

    for i in range(idx,array[0]+1):
        if len(case) > 0:
            if case[-1] >= array[i]:
                continue
        case.append(array[i])
        backTracking(idx+1)
        case.pop()
    return

문제의 조건은 다음과 같습니다.

1) 6개의 수를 뽑아라

2) 사전 순으로 출력하라

 

if len(case) == 6:
    for i in range(6):
        print(case[i],end=' ')
    print()
    return

1번 조건을 만족시키기 위해, 출력할 value들을 담은 배열의 길이가 6일 경우 출력하도록 세팅하였습니다.

 

for i in range(idx,array[0]+1):
    if len(case) > 0:
        if case[-1] >= array[i]:
            continue
    case.append(array[i])
    backTracking(idx+1)
    case.pop()
return

backTracking은 다음과 같이 구성하였습니다.

먼저 2번 조건을 만족 시켜주기 위해, 뽑은 숫자를 저장하는 case 배열에 역순으로 수가 담기지 못하도록 조건문을 설정해주었습니다.

 

이후, 주어진 수열의 값을 백트래킹 기법을 통해 탐색하도록 하여 모든 경우의 수를 출력할 수 있도록 하였습니다.