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

Problem

9개의 키 값들이 들어오면, 7개의 경우의수를 더해 100을 맞추는 문제

Solution

dfs를 통한 브루트포스 탐색으로 합이 100이면 프로그램 종료

코드설명

1)visited 배열과 dfs을 통해 기존에 한번 탐색한 노드는 방문하지 않고 dfs를 수행

2)깊이가 7이고 합이 100이면 출력후 프로그램 종료

이 과정은 visited배열을 이용하는거 자체가 비효율적. idx값을 통해 dfs과정을 수행하게 되면 시간복잡도를 줄일수 있음

Python Code

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

import sys

arrList=[]
visited=[False]* 9

for _ in range(9):
    tmp=int(sys.stdin.readline())
    arrList.append(tmp)
arrList.sort()
result=[]

def dfs(depth,sum,arrList):
    if depth==7:
        if sum==100:
            for re in result:
                print(re)
            exit(0)
    else:
        for i in range(0,len(arrList)):
            if not visited[i]:
                visited[i]=True
                result.append(arrList[i])
                dfs(depth+1,sum+arrList[i],arrList)
                visited[i]=False
                result.pop()
dfs(0,0,arrList)