백준 6603 로또 문제풀이

문제 소개

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

6603번: 로또

 

 

문제 접근 방식

s 집합에서 6개의 숫자를 골라서 모든 경우를 만드는 문제이며 완전탐색 문제임을 알 수 있다.

조합 라이브러리를 써도 되며, 재귀함수를 사용해서 풀어도 되는데 재귀 연습을 위해 후자의 방법을 사용해서 구현했다.

 

 

코드

import sys

input=sys.stdin.readline
print=sys.stdout.write
def dfs(current, count):

    # 선택한 숫자가 6개가 되었다면, 해당 경우의 수를 출력한다.
    if count==6:
        print(' '.join(map(str,selected))+'\n')
        return

    # s 그룹에서 현재 숫자 이후에 위치한 숫자들 중 하나를 뽑아서 dfs를 재귀호출한다.
    for i in range(current+1,k):
        if visited[i]==0:
            selected.append(s[i])
            visited[i]=1
            dfs(i,count+1)
            selected.pop(-1)
            visited[i] = 0


if __name__=='__main__':

    global k,s,selected, visited
    while 1:
        s=list(map(int,input().split()))
        k=s.pop(0)
        selected=[]
        visited=[0]*len(s)

        dfs(-1,0)
        print('\n')
        if k==0:
            break

 

 

회고

이전 문제들에서는 파이썬 global 명령어를 사용하는 방법을 몰라서 매개변수로 설정해서 넘겨줬는데

이번에는 global 사용법에 대한 공부를 하며 문제를 풀었음.

global 명령어는 먼저 실행될 함수에서 

global x 

이런식으로 선언해주면 이후 진행되는 코드에서는 x 를 이용해서 사용할 수 있다.