타겟 넘버

내 풀이

문제 풀이 아이디어

더하거나 빼기 밖에 없다면 결국 모든 경우의 수가 2의 n승개가 나오지 않을까?
그러면 경우의 수가 증가 될 때마다 기존의 경우의 수에 * 2를 해주고 거기에 또 다른 경우의 수를 더하다가 결국 List의 맨마지막에 이르면 모든 경우의 수가 나오지 않을까?

라는 가정으로 착안해서 풀었는데 풀고보니 그냥 완전 탐색인 것 같다.

def solution(numbers, target):
  result = [0]
  cnt = 0
  for n in numbers : 
    result = result * 2
    for i in range(len(result)) :
      if i < len(result) / 2 :
        result[i] += n
      else :
        result[i] -= n
      
  for r in result :
    if r == target :
      cnt += 1 
      
  return cnt

DFS

내가 DFS나 BFS를 사용해서 풀지 못한 가장 큰 원인은 함수를 반드시 하나(문제에서 주어진)만 써야 한다는 강박이 있었고 함수를 커스텀하지 못한 유연한 사고의 결여 때문인 것 같다.

resultList = []
# DFS
def DFS(curValue, numbers, idx, target) : 
  if idx == len(numbers) :
    if curValue == target :
      resultList.append(curValue)
    return 
  DFS(curValue + numbers[idx], numbers, idx + 1, target)
  DFS(curValue - numbers[idx], numbers, idx + 1, target)
  
  return len(resultList)
  
def solution(numbers, target) :
  return DFS(curValue=0, numbers=numbers,idx=0,target=target)

BFS

from collections import deque
def BFS(valueList, target) :
  q = deque()
  cnt = 0
  q.append((valueList, cnt))
  while q :
    valueList, curValue = q.popleft()
    if len(valueList) == 0 :
      if curValue == target :
        cnt += 1
        
      continue
        
    q.append((valueList[1:], curValue + valueList[0]))
    q.append((valueList[1:], curValue - valueList[0]))
    
  return cnt 
def solution(numbers, target):
  return BFS(valueList=numbers, target=target)

행렬과 연산 폰켓몬