[프로그래머스 lv 2] 타겟 넘버.py

<문제 설명>

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

코딩테스트 연습 - 타겟 넘버

음이 아닌 정수들이 배열로 나오고, 이 정수 들의 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들 수 있는 방법의 수를 구하면된다. 

 

입출력의 예는 다음과 같다.

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

 

<문제 풀이 아이디어>
우선 계속 더하고 빼면서 타겟과 같아지는 지 비교할 변수를 선언한다. 이것이 현재 값이 될 것이다.

그리고 나는 dfs(재귀 방식)으로 문제를 해결할 것이기 때문에 dfs 함수를 선언한다.

이 함수에서는 타겟이랑 현재 값이 같은지 비교후, 같지 않다면 dfs 함수를 두번 선언한다. 각각 다음 값을 더하는 dfs, 다음 값을 빼는 dfs 함수를 호출한다.

 

이렇게 정수들을 끝까지 돌았으면 총 몇번 타겟이랑 같은 수가 나오는지 반환한다.

 

<문제 풀이 코드>

def solution(numbers, target):
    answer = 0
    start = numbers[0] #타겟이랑 같아지는지 확인할 변수(현재값)
    answer = dfs(1,start,numbers, target)+dfs(1,-start,numbers, target)
    
    return answer
def dfs(index, start,numbers, target):
        if(index == len(numbers)):#돌만큼 다 돌았다
            if(start == target):
                return 1 #카운트+1(타겟이랑 맞춤)
            else:
                return 0 #카운트 x(조건에 맞지 않음)
        result = 0
        #다음 값을 더하고 빼는 각 경우의 수로 가지침
        result += dfs(index+1, start+numbers[index],numbers, target)
        result += dfs(index+1, start-numbers[index],numbers, target)
        return result

채점 결과