[프로그래머스] 타겟 넘버 (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 이하인 자연수
입출력 예시
| numbers | target | return |
| [1, 1, 1, 1, 1] | 3 | 5 |
| [4, 1, 2, 1] | 4 | 2 |
해결방법
해당 문제를 해결할 때, DFS나 BFS와 같은 그래프 탐색 알고리즘 개념이 부족하다면 조금 어려웠을 것이다.
하지만 문제를 해결하기 위해서 분명한 점은 이 문제는 모든 경우의 수를 탐색해야 한다.
제한 사항의 경우도 크지 않기에, 시간도 그리 오래 걸리지 않을 것이다.
이 문제가 어딜봐서 그래프이고, 어째서 그래프 탐색 알고리즘을 쓰는 거지?
라는 생각을 했다면 조금 다른 관점에서 바라볼 가치가 있다.
그래프 탐색 알고리즘이 아니라, 모든 경우에서 사용 가능한 깊이와 넓이 탐색 알고리즘으로 봐야한다.
본 문제는 모든 경우를 확인해야 한다.
이러한 문제를 쉽게 해결할 수 있도록 제공되는 것은 바로 재귀함수이다.
문제를 해결하기 위해 재귀함수를 구현함에 있어서 필요한 것은 무엇일까.
1. 지금까지 연산된 숫자
2. 현재의 배열에서의 위치 (지금 보고자 하는 숫자)
바로 이 두 가지 이다.
그렇다면, 위 두 가지를 parameter로 갖는 함수를 하나 만들어서 재귀적으로 호출을 해주면 되겠다 !
그렇다. 매우 간단하다. 모든 경우에서 더했을 때의 결과와 뺏을 때의 결과를 고려하여 target과 같은 경우 숫자를 하나씩 더해주면 된다.
재귀함수의 return 구조를 파악한다면, 쉽게 해결할 수 있을 것이다.
정답코드
def solution(numbers, target):
def dfs(index, cur):
if index == len(numbers):
if cur == target:
return 1
else:
return 0
return dfs(index+1, cur + numbers[index]) + dfs(index+1, cur - numbers[index])
return dfs(0, 0)