프로그래머스 Lv2. 타겟 넘버

문제 링크

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

 

풀이

각각의 수를 더하기 혹은 빼기한 경우를 전부 탐색한 후

각각의 수를 계산한 결과가 target이랑 같다면 경우의 수를 1씩 더해준다.

각각의 수를 더하기 혹은 빼기한 경우를 전부 탐색하기 위해 DFS(깊이 우선 탐색)을 이용했다.

 

예시)

[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

 

DFS 함수 설명

    def dfs(result, cnt):

result: 현재까지 계산한 결과값

cnt: 계산한 횟수

 

if 전부 계산했다면

   if 계산값이 목표랑 같다면

      계산값을 구할 수 있는 경우의 수가 1 증가한다.

   그리고 dfs 함수를 종료한다.

        if cnt == len(numbers):
            if result == target:
                nonlocal answer
                answer += 1
            return

 

 

if 계산 중이라면 

   1) 더하기(+)한 경우의 dfs함수를 구한다

      기존 result에서 현재 계산하고자 하는 수(numbers[cnt])를 더한다.

      계산한 횟수 cnt는 1 증가한다

   2) 빼기(-)한 경우의 dfs함수를 구한다

      기존 result에서 현재 계산하고자 하는 수(numbers[cnt])를  뺀다

      계산한 횟수 cnt는 1 증가한다

        elif cnt < len(numbers):
            dfs(result + numbers[cnt], cnt + 1)
            dfs(result - numbers[cnt], cnt + 1)

 

초기값 설정

계산 가능한 경우의 수 answer의 초기값은 0이다.

    answer = 0

 

dfs함수의 파라미터는 각각 0으로 해준다.

처음 계산한 값은 0, 처음 계산 횟수는 0이기 때문이다.

    dfs(0, 0)

 

결과값

DFS 한 이후의 answer의 값을 return한다.

    return answer

전체 코드

def solution(numbers, target):
    answer = 0
    def dfs(result, cnt):
        if cnt == len(numbers):
            if result == target:
                nonlocal answer
                answer += 1
            return
        elif cnt < len(numbers):
            dfs(result + numbers[cnt], cnt + 1)
            dfs(result - numbers[cnt], cnt + 1)
    
    dfs(0, 0)
    
    return answer