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

https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

---

풀이 과정

양수들의 집합 numbers에 들어있는 모든 수를 사용하여 target을 만드는 방법이 몇 가지 있는지를 구하는 문제이다.

 

1. 조합

numbers 내부의 모든 수를 다 더한 뒤 (numbers의 모든 수를 양수로 선택했다고 가정한 뒤) 조합으로 경우의 수를 만들어 보면서 선택한 양수를 음수로 바꿔볼 수 있다.

 

예를 들어 [3, 4, 5, 7]이면 3, 4, 5, 7 전부를 양수로 선택했을 경우의 값은 19이고, 여기서 4를 음수로 선택했다고 가정하면 19 - (4 * 2) = 11이 됨을 고려하며 (3), (4), (5), (7), (3, 4), (3, 5), ... , (3, 4, 5, 7)의 모든 순서쌍을 만들어보며 각 순서쌍 안의 숫자들을 음수로 선택했을 경우의 합을 생각해보고 target과 같은지 판단해 볼 수 있다.

 

2. DFS

[4, 1, 2, 1]이 있으면 DFS로

 

1. 4 혹은 -4를 선택

2. 1 혹은 -1을 선택

3. 2 혹은 -2를 선택

4. 1 혹은 -1을 선택

 

를 점검하면서 4개 모두 골랐을 경우의 합이 target과 같은지 판단하고 같으면 정답의 개수를 증가시키는 방법으로 문제를 해결할 수 있다.

---

소스 코드

1번 방법

from itertools import combinations


def solution(numbers, target):
    sum_value = sum(numbers)
    answer = 0
    target = (sum_value - target) // 2
    for length in range(1, len(numbers) + 1):
        for j in combinations(numbers, length):
            if sum(j) == target:
                answer += 1
    return answer

 

2번 방법

answer = 0


def dfs(numbers, target, discovered=[], depth=0):
    global answer
    if len(numbers) == depth:
        if sum(discovered) == target:
            answer += 1
        return
    dfs(numbers, target, discovered + [numbers[depth]], depth+1)
    dfs(numbers, target, discovered + [numbers[depth] * -1], depth+1)

def solution(numbers, target):
    dfs(numbers, target)
    return answer