[프로그래머스/Python] 타겟 넘버

문제 설명

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 이하인 자연수입니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

 

입출력 예 #2

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

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

---

풀이

1. DFS

answer= 0

def dfs(numbers, target, current, idx):
    global answer
    
    if len(numbers) == idx:
        if target == current:
            answer += 1
        return
    
    dfs(numbers, target, current + numbers[idx], idx+1)
    dfs(numbers, target, current - numbers[idx], idx+1)

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

 

1. DFS는 재귀함수를 사용

2. 현재 값과 위치를 초기 0으로 지정

3. answer는 count 값을 넣는다

4. 현재값에 주어진 numbers 값을 하나씩 더하고 idx값도 증진

5. numbers길이와 idx값이 같을 때, 원하는 target값과 answer가 일치하면 count +1

6. 일치하지 않으면, return하여 그 전 값으로 돌아간다

7. 해당 과정 반복

 

 

2. BFS

def solution(numbers, target):
    answer = 0
    bfs = [0]
    
    for i in numbers:
        temp = []
        
        for j in bfs:
            temp.append(j + i)
            temp.append(j - i)
        bfs = temp
    
    for a in bfs:
        if a == target:
            answer += 1
    return answer

 

1.  모든 값을 저장하기 위한 bfs 생성

2. 위에서부터 numbers의 값을 하나씩 계산

3. 전체의 값을 bfs에 넣은 후, bfs값 중 target과 같은 값이 있으면 count

 

 

문제 출처

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