타겟 넘버
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
-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 |
---|---|---|
[1, 1, 1, 1, 1] | 3 | 5 |
[4, 1, 2, 1] | 4 | 2 |
문제 예시와 같습니다.
+4+1-2+1 = 4
+4-1+2-1 = 4
def solution(numbers, target):
# leaves = [0] # 모든 계산 결과를 담자
# count = 0
# for num in numbers :
# temp = []
# # 자손 노드
# for leaf in leaves :
# temp.append(leaf + num) # 더하는 경우
# temp.append(leaf - num) # 빼는 경우
# leaves = temp
# # 모든 경우의 수 계산 후 target과 같은지 확인
# for leaf in leaves :
# if leaf == target :
# count += 1
# return count
sup= [0]
for i in numbers:
sub = []
for j in sup :
sub.append(j+i)
sub.append(j-i)
sup = sub
return sup.count(target)
def solution(numbers, target):
answer = DFS(numbers, target, 0)
return answer
def DFS(numbers, target, depth):
answer = 0
if depth == len(numbers): # 끝까지 닿았을 때
# print(numbers)
if sum(numbers) == target:# 끝까지 닿은 것 중에서 타겟이랑 같으면
return 1
else: return 0
else: #depth가 0,1,2,3 일 때
#answer = 0
answer += DFS(numbers, target, depth+1)
numbers[depth] *= -1
answer += DFS(numbers, target, depth+1)
print(answer)
return answer
def solution(numbers, target):
answer = 0
queue = [[numbers[0],0], [-1*numbers[0],0]]
#[[4,0], [-4,0]]
n = len(numbers) # n =4
print(queue,n)
while queue:
temp, idx = queue.pop()
idx += 1
# print(temp,idx)
if idx < n:
print([temp+numbers[idx], idx],[temp-numbers[idx], idx])
queue.append([temp+numbers[idx], idx])
queue.append([temp-numbers[idx], idx])
print(queue)
else:
if temp == target:
answer += 1
return answer
def solution(numbers, target):
def dfs(level,current_sum ,answer):
if level >= len(numbers):
if current_sum == target:
answer += 1
return answer
answer = dfs(level+1, current_sum + numbers[level], answer)
answer = dfs(level+1, current_sum - numbers[level], answer)
return answer
return dfs(0,0,0)
dfs의 else 부분이 이해가 안간다....왜지...도대체 왜지,...
#이진수 풀이법
def solution(n, t):
answer = 0
for i in range(2**len(n)):
tmp = []
for j in range(len(n)):
if i & (2**j) == 0:
tmp.append(n[j])
else:
tmp.append(-1*n[j])
if sum(tmp) == t:
answer += 1
return answer