Level 2. 타겟 넘버

04. 타겟 넘버

코딩테스트 연습 > DFS,BFS > 타겟 넘버
https://programmers.co.kr/learn/courses/30/lessons/43165

---

문제 설명

Input value =

• numbers = n개의 양수 리스트

• target = 목표 값

Process =

• 리스트의 숫자를 적절히 더하고 빼서 target 값 생성

Output value =

• 될 수 있는 경우의 수

---

제한 사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.

• 각 숫자는 1 이상 50 이하인 자연수입니다.

• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

---

문제 구상

#00
numbers = [1,1,1,1,1]
target = 3

1. DFS 함수 작성

#01
array = [0]
def dfs(n):
    global array
    sub_array = []
    for i in array:
        sub_array.append(i+n)
        sub_array.append(i-n)
        array = sub_array
    return array

02.target 에 맞는 값을 카운팅한다.

#02
for n in numbers:
    result = dfs(n)
#03
result.count(target)

---

문제 풀이

구상한 방법을 이용

array = [0]
def dfs(num):
    global array
    sub_array = []
    for i in array:
        sub_array.append(i+num)
        sub_array.append(i-num)
        array = sub_array
    return array

def solution(numbers,target):
    for i in numbers:
        result = dfs(i)
    return result.count(target)

# Code test
numbers,target = [1,1,1,1,1],3
solution(numbers,target)

itertools의 product를 이용

product를 이용하여 구할 수 있는 모든 경우를 구한 후
target 에 맞는 값을 카운팅한다.

from itertools import product

def solution(numbers,target):
    l = [(x,-x) for x in numbers]
    s = list(map(sum,product(*l)))
    return s.count(target)

# Code test
numbers,target = [1,1,1,1,1],3
solution(numbers,target)