[프로그래머스] 타겟 넘버 (lv.2)

문제

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
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

---

풀이

def solution(numbers, target):
    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)

 

---

다른 풀이

a = 0

def dfs(i, result, numbers, target) :
    global a
    if i == len(numbers) :
        if result == target : 
            a+=1
            return
    else :
        dfs(i+1, result+numbers[i], numbers, target)
        dfs(i+1, result-numbers[i], numbers, target)

def solution(numbers, target):
    result = 0
    dfs(0, result, numbers, target)
    
    return a

 

---

설명

1. 원소에 하나씩 접근하면 되겠다는 생각은 했으나, 어떤 방식으로 해야할지 가늠이 오지 않았었음.

## 아이디어

노드 엣지로 구성된 그래프를 그릴 수 있는 상하좌우, map 문제 뿐 아니라 이런 것도 bfs/dfs 문제임을 깨닫게 해준 문제. 이진 트리 형식으로 뻗어나갈 수 있는 문제는 dfs/bfs로 접근할 수 있음을 항상 염두해 두어야겠다. 

이 문제의 접근방식을 손그림으로 표현하면 다음과 같다. 가장 main idea는 +, - 부호에 따른 각 숫자에서 2가지 경우의 수가 생산된다는 것이다. 따라서 numbers의 각 숫자에 따라 2가지 경우로 자손을 뻗을 수 있게되고, 모든 경우의 수를 탐색하는 bfs/dfs 문제가 된다.

 

2. 위의 넓이 우선 탐색을 이용한 것이라고 보면 이해하기 쉽다.
먼저 super node로 [0]을 하나 만들어 두고 [0+1] [0-1] 로 sub node 두개를 생성한다.
이렇게 생성된노드 super node로 저장되고, 
저장된 super node는 for문을 돌면서 [0+1+1] [0+1-1] , [0-1+1] [0-1-1] 를 거치면서 super node에 다시 저장된다.

이런 방식으로 전체 저장되는 리스트가
[5, 3, 3, 1, 3, 1, 1, -1, 3, 1, 1, -1, 1, -1, -1, -3, 3, 1, 1, -1, 1, -1, -1, -3, 1, -1, -1, -3, -1, -3, -3, -5]
이 되고 여기에서 target number인 3의 개수를 count 로 찾으면 된다.