[백준/python] 2309번 : 일곱 난쟁이

문제

 

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

2309번: 일곱 난쟁이

---

Algorithm

 

1. 7명을 뽑아 합을 조사할 새로운 리스트 선언

2. 만약 7번 재귀를 돌았다면 & 현재 저장된 일곱난쟁이들의 합이 100이라면 오름차순으로 정렬 후 출력

3. 만약 7명을 뽑았는데 합이 100이 아니라면 해당 재귀를 더이상 실행하지 않고 종료

4. 시작인덱스와 9명의 난쟁이가 있으므로 9번을 돈다.

5. 난쟁이 한명을 추가한다.

6. dfs를 돈다(다음번 깊이는 +1로 해주고 인덱스는 중복되지 않게 하기위해서 다음 인덱스를 넣어준다.)

7. dfs를 돌다 7명이 다 찼으나 합이 100이 아니어서 return 되었으면 넣었던 난쟁이 한명을 다시 빼준다.

8. dfs를 돈다.

---

 

 

Code

short_men = [int(input()) for _ in range(9)]
seven_short_temp = [ ]  


def dfs(depth, start):
    if depth == 7:  
        if sum(seven_short_temp) == 100:  
            for j in sorted(seven_short_temp):  
                print(j)
            exit()  
        else:  
            return  

    for i in range(start, len(short_men)): 
        seven_short_temp.append(short_men[i])  
        dfs(depth + 1, i + 1)  
        seven_short_temp.pop() 


dfs(0, 0)