사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.각 숫자는 1 이상 50 이하인 자연수입니다.타겟 넘버는 1 이상 1000 이하인 자연수입니다.
입출력 예 numbers target return [1, 1, 1, 1, 1] 3 5
입출력 예 설명 문제에 나온 예와 같습니다.
answer = 0# DFS 이용defdfs(idx, result, numbers, target):global answer
if idx == len(numbers): # numbers 원소를 모두 계산했을 경우if result == target:
answer += 1returnelse:
dfs(idx + 1, result + numbers[idx], numbers, target) # 재귀구조
dfs(idx + 1, result - numbers[idx], numbers, target)
defsolution(numbers, target):global answer # 전역 변수 사용
dfs(0, 0, numbers, target) # result = 0으로 초기화return answer
해당 문제는 DFS/BFS 등의 완전탐색을 통해 해결해야 하는 문제다. 어찌됐든 가능한 모든 값을 펼쳐놓고 target값과 일치하는 경우의 수를 더하여 결과값을 출력하면 된다.
DFS - numbers 원소를 차례대로 더하거나 빼서 만들 수 있는 수를 가지치기 형식으로 생각하면 된다.
- numbers 원소만큼 모두 계산해서 최종값(위 코드에선 result 변수)이 target과 같아지면 answer에 1을 더하면 된다. - numbers 원소만큼 다 계산했는지는 인덱스로써 판단한다.
위 코드는 재귀구조를 통해 DFS를 구현했지만, 스택(stack) 자료구조를 통해 DFS를 구현할 수도 있다. 하지만 아래 "테스트 통과" 화면을 참고하면 재귀구조가 비교적 빠르다는 것을 알 수 있다.