[프로그래머스] 타겟넘버
문제 설명
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 함수를 작성해주세요.
https://school.programmers.co.kr/learn/courses/30/lessons/43165
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
문제 풀이
2가지 방법으로 풀이할 수 있습니다.
1. 모든 조합을 계산해서 target 과 동일한 값의 개수 찾기
2. DFS
저는 DFS 로 문제를 풀어보았습니다.
사실 DFS 문제가 처음이라서 여러 풀이들을 참고해서 풀어보았어요. 참고한 링크는 밑에서 확인하실 수 있습니다.
함수 내부에서 함수를 다시 호출하는 재귀함수 형식입니다.
number 원소를 각각 더하거나 뺄 수 있기 때문에 +, - 두가지 모두를 재귀함수로 호출합니다.
그러면 내부에서 현재 결과(i번째 원소까지의 합)를 기준으로 그 다음 원소에 대해 다시 +, - 두가지를 모두 호출하기 때문에 모든 경우의 수를 탐색할 수 있게 됩니다!
def solution(numbers, target):
global answer
answer = 0
total = 0; i = 0
# 재귀함수
def sum(i, numbers, total, target):
global answer
if i == len(numbers):
if total == target:
answer += 1
return
sum(i+1, numbers, total + numbers[i], target)
sum(i+1, numbers, total - numbers[i], target)
return
sum(i, numbers, total, target)
return answer
[ref]
[1] https://blog.naver.com/jmc0820/223346499460