[고득점 kit]_DFS/BFS_#1. 타겟 넘버

문제 설명

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 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예numberstargetreturn

[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

---

( 문제 해설 )

 

* 내 생각

0. 이 주제에서 개념적인 부분의 알고리즘 문제

1. dfs/ bfs 자체가 처음 맞이하면 쉽지 않기 때문에 쉽다고 볼 수는 없는 문제입니다.

 

* 문제 요구

2. 해당 숫자를 모두 연산합니다 (+, -)

3. 연산을 하면서 목표가 되는 값이 몇개 출력되는지가 문제입니다.

 

* 문제 해결 알고리즘

4. for문을 돌든 무엇을 돌든 숫자를 순회해야 합니다

5. 각각 +, - 연산을 선택해서 수행하고

6. 모두 순회가 됐고 그 값이 목푯 값이면 answer += 1

7. for 문이나 while 문으로 순회하는 것도 방법이겠지만 이 문제는 dfs를 재귀를 써서 푸는 게 쉽습니다.

8. 이유는 재귀이기 때문에 모두 순회했을 때 리턴한 이후 바로 이전으로 가서 +를 먼저 했다면 - 연산을 하게 하기가 쉽기 때문입니다.

**기본적인 dfs 개념을 알고 있다면 코드를 보는 게 더 쉬울 것입니다**

 

---

[ 코드 ]

 

answer = 0
def dfs(summary ,numbers, target, cnt):
    global answer
    if len(numbers) == cnt:
        if summary == target:
            answer += 1
            return

    if cnt >= len(numbers):
        return

    dfs(summary + numbers[cnt], numbers, target, cnt + 1)
    dfs(summary - numbers[cnt], numbers, target, cnt + 1)


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

 

혹시 전역 변수 사용이 헷갈리시는 분이 있을 수 있기 때문에 전역변수 사용 법만 알려드리자면

전역변수 이전에 가장 최단 밖에 위치에 변수를 선언을 한 후

그 내부에 전역변수 초기화를 해야 사용할 수 있습니다.

 

 

---

후기

 

개념 다지기 좋은 문제입니다.

설명할 것도 업는 깔끔한 재귀 코드

하지만 처음 보시는 분은 다소 어려울 수 있습니다.