[DP] 백준 6603번 로또 (Python)

 

 

생각하기

처음 이 문제를 보고서는 브루트포스 문제라고 생각하고 for문을 중첩하여 풀어야겠다고 생각했다

12345678 이면 678을 67, 68, 78 이렇게 for문으로 처리해야지!

하지만 For문으로 처리하려다 보니까 난리도 아니었다.. 너무 코드가 더러워졌다

더러워지면 질수록 이건 틀린거다..! 

그래서 다시 뒤엎고 생각을 했다. 

다시한번 잘 보니 이 문제는 DFS 문제였다 사실 어떻게보면 DFS도 모든 경우의 수를 들여다 보는 것이기 때문에 크게 보면 브루트포스에 속하긴한다

브루트포스라고 해서 다 for문 돌리는건 아니다!

구현하기

input으로 들어온 각 수를 돌면서 dfs를 하면 된다

• depth : 총 여섯자리까지 구하면 되는 것이기 때문에 Dfs에서 깊이는 6까지만 찍고 올라오면 된다
• output 배열 : dfs에서 depth가 6이되면 결과 값들을 출력해야 하는데 이때, 결과값들을 저장하고 있는 리스트가 필요하다. return을 통해 돌아올 때, Pop을 해서 탐색을 마친 숫자를 없애주는 기능을 가지고 있고 새로운 수에 도달했을 때, append를 통해서 추가해주는 기능도 있다
• limit : dfs를 실행하다가 배열을 초과해버리는 문제를 방지하기 위해 들어가 숫자의 개수를 가지고 있는 Limit 변수

import sys
input = sys.stdin.readline


output = []

def DFS(arr, output, idx, depth, limit):
    if depth == 6:
        output.append(arr[idx])
        for i in output:
            print(i, end=' ')
        print()
        output.pop()
        return
    else:
        if idx <= limit:
            output.append(arr[idx])
            # 현재 노드보다 무조건 커야함
            for i in range(idx+1, limit+1):
                DFS(arr, output, i, depth+1, limit)
            output.pop()
            return
        else:
            return
            
        


while True:
    input_data = list(map(int, input().split()))
    if input_data[0] == 0:
        break
    k = input_data[0]

    for i in range(1, k+1):
        DFS(input_data, output, i, 1, k)
        output.clear()
    
    print()