문제
n개의 음이 아닌 정수들이 있습니다.
이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.
예를 들어, [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
- +1 + 1 + 1 + 1 - 1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때,
숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성하세요.
제한사항
- 숫자의 개수: 2개 이상 20개 이하
- 각 숫자: 1 이상 50 이하 자연수
- 타겟 넘버: 1 이상 1000 이하 자연수
입출력 예
| numbers | target | return |
| [1, 1, 1, 1, 1] | 3 | 5 |
| [4, 1, 2, 1] | 4 | 2 |
입출력 예 설명
예시 #1
문제에서 제시된 예와 같습니다.
예시 #2
- +4 + 1 - 2 + 1 = 4
- +4 - 1 + 2 - 1 = 4
총 2가지 방법이 있으므로 2를 return 합니다.
풀이
문제에서 중요한 점은 주어진 숫자의 순서를 바꾸지 않고, 각 숫자를 더하거나 빼는 두 가지 선택지로 탐색해야 한다는 것이다.
이를 보고 깊이 우선 탐색(DFS) 아이디어를 떠올렸다.
- 각 깊이에서 현재 숫자를 + 또는 - 하는 두 가지 경우로 분기한다.
- 마지막 인덱스까지 탐색했을 때 누적 결과가 target과 일치한다면 경우의 수를 증가시킨다
첫 풀이는 answer을 매개변수로 지정하여, 자식 노드에서 업데이트된 값을 부모로 반환하고, 두 갈래(+, -)의 결과를 합치는 방식으로 작성하여 통과했다. 그러나 다른 풀이들을 보며 answer 변수를 파라미터로 전달하면서 갱신이 불필요하다는 것을 깨달았다.
def solution(numbers, target):
answer = 0
def dfs(i, result, answer):
n = numbers[i]
if i == len(numbers) - 1:
if result - n == target or result + n == target:
answer += 1
elif i < len(numbers) - 1:
answer = dfs(i + 1, result - n, answer) + dfs(i + 1, result + n, answer)
return answer
answer = dfs(0, 0, answer)
return answer
두 번째 풀이에서는 answer 파라미터를 제거하고, dfs 함수가 경우의 수만 반환하도록 개선하였다.
def solution(numbers, target):
def dfs(i, result):
n = numbers[i]
if i == len(numbers) - 1:
return 1 if result - n == target or result + n == target else 0
else:
return dfs(i + 1, result - n) + dfs(i + 1, result + n)
return dfs(0, 0)