[Python] 파이썬 프로그래머스 타겟 넘버

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

재귀 함수를 통해 [+,-] 두 개의 리스트를 만들어 각 branch에서 앞의 수에 누적으로 자신의 수를 더하고 빼서 문제를 품

---

num_target = []
def bfs_target(num, a_num,numbers):
    global num_target
    a = [a_num for _ in range(2)]
    if num < 0:
        num_target.append(a[0])
        return
    else:
        a[0] += numbers[num]
        a[1] += numbers[num]
        bfs_target(num-1, a[0], numbers)
        a[1] -= (numbers[num]*2)
        bfs_target(num-1, a[1], numbers)

def solution(numbers, target):
    bfs_target(len(numbers)-1, 0, numbers)
    answer = num_target.count(target)
    return answer

---

다른 사람의 풀이

재귀용법에 아직 미숙해서 위와 같이 각 재귀마다 list를 만들어서 더하고 빼기를 진행하였는데 위와 같이 시용하면 list 생성을 매 순간마다 해줘야 한다.

 

아래의 방법은 최척화 된 코드이다.

 

return solution(solution() + solution()) 이런 식으로 사용하면 되는데 if 문으로 0과 1을 반환하는 것을 생각하지 않고 더해지거나 뺀 수를 생각하여 위와 같이 적었다..ㅜ 다음부터는 종이에 적어가면서 문제를 풀어야겠다.

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])