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

 

문제 풀이 설명

아이패드로 number의 변화와 target의 변화를 나타내 본다면 아래와 같다.

그래서 위의 내용을 함수로 나타내면, 아래와 같다. 

아 재귀함수에 대한 글을 보면 쉽게 이해할 수 있다. (재귀함수 쉽게 사용하는 방법 알아보기)

 

소스 코드

def solution(numbers, target):

    if len(numbers) == 0:

        if target == 0:

            return 1

        else:

            return 0

 

return solution(numbers[1:], target+numbers[0]) + solution(numbers[1:], target-numbers[0])

 

재귀함수의 의미는 numbers라는 list와 target의 변수를 넣었을 때, 타겟에 맞는 개수를 반환한다. 

리스트가 없는 경우로 종료되는 조건문을 우선적으로 작성한다.

numbers리스트 길이가 0인 경우는 두가지 경우가 있다. 

target이 0인경우는 1개를 찾아낸 것이고 target이 0이 아니면 0을 리턴한다. 

최소의 조건을 만족하는 종료문을 작성한 뒤에는

리스트 맨 앞자리를 +로 했을 경우의 개수와 리스트 맨 앞자리를 -로 했을 경우의 개수를 더하도록 반환한다. 

이렇게 함수를 돌리게 되면 결과값을 모두 구할 수 있는 함수가 된다.