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

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

프로그래머스

 

[문제 이해]

주어진 숫자들을 활용하여 덧셈 혹은 뺄셈 만을 사용하여 target에 해당하는 숫자가 결과 값으로 나오도록 계산할 수 있는 가짓 수를 세는 문제였다. 예를 들어, 

-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가 [1, 1, 1, 1, 1] 로 주어졌을 때 target이 3이 되는 방법은 위와 같이 5가지가 된다.

 

[문제 풀이]

DFS, BFS 중 하나로 풀기 위해서 트리를 구상해봤는데 루트 노드를 0이라고 했을 때, 다음 레벨에는 numbers의 첫 번째 원소가 자식 노드로 오는데 이때 양수와 음수로 각각 나눠지면 된다. 

왼쪽 그림과 같이 생각은 했지만 막상 구현하려니 DFS를 사용하는 것 말고는 어떻게 풀어야 할지 감이 안와서 구글링을 통해 다른 사람들의 코드를 참고하여 풀었다.

 

dfs의 매개변수로 numbers의 원소를 탐색하는 인덱스와 현재까지의 합을 넣어주어 구현하는 dfs 함수 내에서 적절한 처리를 할 수 있도록 한다. dfs 함수 내에서는 먼저 cnt(타겟넘버로 결과값이 나오는 가짓 수)를 전역 변수로 사용하여 따로 매개변수로 넣을 필요 없이 dfs를 호출한 쪽에서도 값을 유지할 수 있도록 한다. 만약 탐색하고 있는 인덱스 번호가 numbers의 길이랑 동일하다면 numbers에 대한 탐색이 끝난 것이므로, 현재까지 더해진 값과 타겟으로 지정했던 값을 비교해서 같다면 타겟넘버에 도달했으므로 cnt의 값을 하나 올리고 그렇지 않으면 동작 없이 return한다. (이미 numbers는 다 돌았으니 함수 종료)

만약 탐색해야할 numbers의 원소가 남아있다면 재귀적으로 dfs를 호출하되, 현재까지 더해진 값에 numbers의 인덱스 번호에 해당하는 원소를 더하더나 빼줘서 확인해야할 두 가지를 모두 구현할 수 있다. 인덱스는 다음에 탐색할 numbers의 원소에 해당하는 인덱스이므로 재귀적으로 호출하는 dfs 함수의 인자로는 idx+1으로 넣어주어야 한다. 최종 코드는 아래와 같다.

 

[최종 코드]

cnt = 0 # global로 사용

def dfs(numbers, target, current, idx):
    global cnt
    if idx == len(numbers): # numbers를 모두 거쳤을 때
        if current == target: # target이랑 현재 값이 같으면 
            cnt += 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 cnt

 

나는 dfs로 풀었지만 bfs로도 풀 수 있다!