문제:
출처: 프로그래머스 - 타겟 넘버
문제설명:
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 이하인 자연수입니다.
입력 예1:
numbers : [1, 1, 1, 1, 1]
target : 3
return : 5
입력 예2:
numbers : [4, 1, 2, 1]
target : 4
return : 2
출력 예 #2
+4+1-2+1 = 4
+4-1+2-1 = 4
풀이:
DFS문제로 입력으로 주어진 리스트 numbers 안의 원소에 마이너스('-')를 붙이는 모든 경우의 수를 확인하여, 리스트 numbers의 원소들의 합이 target과 같은 경우가 몇 번이 있는지 확인하는 문제다.
숫자의 개수의 길이는 20 이하의 길이를 가지며, 재귀를 통해 풀더라도 빅오표기법 O(2**N)으로 엣지컷트가 없더라도 연산횟수에는 문제가 없다. N이 최대 20으로 설정하더라도 연산횟수는 약 100만회를 조금 넘어간다.
리스트 numbers의 인덱스 길이, 즉 N만큼의 깊이를 지닌 이진트리로 마이너스를 붙이는 경우와 붙이지 않는 경우로 나누어 탐색을 하면된다. 마지막 리프 노드에 도달했을 시 numbers 원소들을 모드 더한 값과 target이 같으면 count를 1씩 올려주면 된다.
이런 방식은 부분집합을 구하는 방식과 같다. 부분집합에 마이너스를 붙여주면 그 상황이 모든 마이너스를 붙이는 경우의 수와 같다.
참고 : 재귀로 부분집합 구하기
코드:
def solution(numbers, target):
n = len(numbers)
answer = 0
#DFS() 함수는 밖으로 빼도 무관하다.
def DFS(lv, sumN): # return이 없으며, answer의 값을 업데이트만 한다.
nonlocal answer
if lv == n:
if sum(sumN) == target:
answer += 1
else:
DFS(lv + 1, numbers) # 마이너스를 붙이지 않는 방향으로
numbers[lv] = -numbers[lv] # 깊이 level과 numbers의 인덱스와 일치한다. 그 값을 마이너스로 바꾼다.
DFS(lv + 1, numbers) # 마이너스를 붙이는 방향으로
numbers[lv] = -numbers[lv] # 바꾼 마이너스는 다시 원래대로 돌리는 구간
DFS(0, 0) # 재귀 함수 호출 부분
return answer