🔗 문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/43165
문제 설명
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(깊이 우선 탐색)가 적합
시간 복잡도
각 숫자마다 2가지 선택 → O(2^n)
n은 최대 20이므로 2^20 = 약 100만 번의 연산 (충분히 가능)
DFS 풀이 전략
1. 재귀 함수 설계
dfs(현재 인덱스, 현재까지의 합)현재 인덱스: 지금 처리할 숫자의 위치
현재까지의 합: 이전까지 계산된 합계
2. 탐색 트리 구조
(0, 0)
/ \
+1 -1
(1, 1) (1, -1)
/ \ / \
+1 -1 +1 -1
(2,2) (2,0) (2,0) (2,-2)각 노드에서 두 갈래로 분기되며, 모든 경로를 탐색
전체 코드
def solution(numbers, target):
answer = 0
def dfs(index, cur_sum):
nonlocal answer
# 종료 조건: 모든 숫자를 다 사용했을 때
if index == len(numbers):
if cur_sum == target:
answer += 1
return
# 현재 숫자를 더하는 경우
dfs(index + 1, cur_sum + numbers[index])
# 현재 숫자를 빼는 경우
dfs(index + 1, cur_sum - numbers[index])
dfs(0, 0)
return answer코드 설명
1. 초기화
answer = 0 # 경우의 수를 저장할 변수2. DFS 함수 정의
def dfs(index, cur_sum):
nonlocal answer # 외부 변수 수정을 위해 필요nonlocal: 중첩 함수에서 외부 함수의 변수를 수정하기 위한 키워드
3. 종료 조건
if index == len(numbers):
if cur_sum == target:
answer += 1
return모든 숫자를 다 사용했을 때 (
index == len(numbers))현재 합이 타겟과 같으면 경우의 수 증가
4. 재귀 호출
dfs(index + 1, cur_sum + numbers[index]) # 더하기
dfs(index + 1, cur_sum - numbers[index]) # 빼기중요: 더하든 빼든
index + 1로 다음 숫자로 이동index - 1이 아니라index + 1
실행 과정 예시
numbers = [1, 1, 1], target = 3인 경우:
dfs(0, 0)
→ dfs(1, 1) # +1
→ dfs(2, 2) # +1
→ dfs(3, 3) # +1 → target 달성! ✓
→ dfs(2, 0) # -1
→ dfs(3, 1) # +1
→ dfs(1, -1) # -1
→ dfs(2, 0) # +1
→ dfs(3, 1) # +1
→ dfs(2, -2) # -1
→ dfs(3, -1) # +1