[프로그래머스] Python - 타겟 넘버

코딩테스트 연습 - 타겟 넘버

 

프로그래머스의 DFS/BFS 레벨2 문제다.

숫자들이 리스트로 주어지고 각 숫자들을 서로 더하거나 뺀 결과가 타겟과 같은 경우가 몇 개 인지 확인하는 문제다.

 

# target is 3

numbers = [1,1,1,1,1]

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

여러 경우의 수 중 위와 같이 타겟인 값을 찾아야 한다.

나는 DFS를 이용해서 풀었다.

위의 예시 처럼 numbers가 주어지면 각 원소마다 + 또는 -연산을 수행하고 결과를 누적하는 DFS의 재귀를 통해 구현하였다.

 

solution 함수에서 dfs 함수에 진입하는 부분에서 2번 접근이 이루어지다보니 값이 2배가 되어서 결과를 2로 나누었다.

 

 

 

GitHub - Floodnut/Algorithm: 알고리즘 풀이 모음