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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

본 문제를 간단히 설명하자면 다음과 같다.

숫자를 담고 있는 numbers라는 배열과 숫자 target이 주어진다. 이때 numbers 숫자의 부호를 랜덤하게 설정하여 모두 더했을 때, target가 되는 경우의 수는 몇 개인지를 구하는 것이다.

 

코드를 작성하기 위한 순서는 다음과 같다.

1. 모든 경우의 수를 구해야하기 때문에 DFS 재귀함수를 만들어준다.

2. DFS 함수에서 더한 값이 target과 같고 호출한 횟수가 numbers의 배열 크기와 같다면 count를 해준다.

3. 만약 호출한 횟수만 numbers의 배열 크기와 같다면 target과 다르기에 count하지 않는다.

 

필자가 작성한 코드는 다음과 같다.

def solution(numbers, target):
    global count #dfs함수를 사용하기 위해 전역변수 count를 설정하였다.
    count=0
    num=len(numbers)
    
    def dfs(index, numbers, total):
        global count
        if index==num and total == target: #2번 : 다음과 같은 조건일 때, 배열의 모든 원소의 합이 target과 같으므로 count++을 해주고 종료한다.
            count+=1
            return
        if index==num: #3번 : 배열 순회만 완료하고 합은 target과 같지 않은 경우이므로 count하지 않는다.
            return
        dfs(index+1, numbers, total+numbers[index]) #index를 하나 추가시키고, total+numbers[index]를 사용하여 +부호로 DFS를 돌린다.
        dfs(index+1, numbers, total-numbers[index]) #index를 하나 추가시키고, total-numbers[index]를 사용하여 -부호로 DFS를 돌린다.
    
    dfs(0, numbers, 0) #처음 DFS를 실행할 때는 처음부터 순회해야하기 때문에 index=0이고 total=0으로 실행시켜준다.
    
    return count

DFS를 사용하면 간단하게 풀 수 있는 문제였다.

하지만 필자는 총 더한 값인 total을 DFS함수의 인자로 두고, 음수일 때와 양수일 때를 total+-numbers[index]로 두어 조금 더 간단하게 코드를 작성하였다.