[백준/Python] 3040. 백설 공주와 일곱 난쟁이

🍀 문제유형: 브루트포스/ DFS 

🍀  문제설명(링크참조) 

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

🍀  풀이코드 

# 방법1. DFS 

# 11:35 start 56 end
# dfs..
def dfs(i, total, result, cnt):
    global answer
    if cnt == 7:
        if total == 100 :
            answer = result
            return
    if i == 9:
        return # cnt = 7 이지만 100이 아니면 멈춰야 해
    #i 포함 X
    dfs(i+1, total, result, cnt)
    #i 포함 O
    dfs(i+1, total+nums[i], result+" "+str(nums[i]), cnt+1)

nums = []
answer = ""
for _ in range(9):
    nums.append(int(input()))

dfs(0, 0, "", 0)
for i in answer.split():
    print(i)

 

RecursionError: maximum recursion depth exceeded in comparison 이런 에러가 떴었다. 

빠져나올 구멍을 다 안 만들어서이니까.. 구글링을 조금 했다. 대부분 브루트포스로 쉽게 풀이하셨지만, dfs로도 풀어보고 싶었다..ㅎㅎ 여튼 그래서 살펴보니까 9명 중 7명을 선택한다/ 9명 모두 살펴봤지만 100이 아닐 수도 있다 이 조건을 놓치고 있었다. cnt 를 인자에 추가해 7명일 때 100인지 살펴볼 수 있게 했고, 아래 코드를 추가해 2번째 조건도 해결하니까 맞출 수 있었다. 

 

dfs 풀이할 때 주의할 점은 꼭 정답일 때만 탈출하는 것이 아니니까, 그 외에 인덱스 오버 될 때 또는 또 다른 조건을 만족할 때는 return 할 수 있도록 만들어야 한다. 

if i == 9: return

 

# 방법2. 브루트포스 

from itertools import combinations
nums = []
for _ in range(9):
    nums.append(int(input()))

# dfs(0, 0, "", 0)
for l in combinations(nums, 7):
    if sum(l) == 100:
        for i in l: print(i)