문제링크 : programmers.co.kr/learn/courses/30/lessons/43165
코딩테스트 연습 - 타겟 넘버
n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+
programmers.co.kr
재귀를 통한 dfs를 이용했다. 리스트를 잘라가며 재귀에 넘겨주므로 재귀 탈출 조건으로 numbers가 빈 리스트인 경우로 설정하였다. 인자에 있는 numbers는 계산을 하기 위해 남은 숫자 리스트, sum은 현재 재귀에서의 합을 뜻한다.
그리고 입력한 숫자에 대해서 +와 -모두 고려해야 되므로 현재 sum에 -한 값과 +한 값을 sum_1, sum_2로 설정하여 이용한다.
count = 0 def dfs(numbers, target, sum): global count if len(numbers) == 0: return sum_1 = sum - numbers[0] sum_2 = sum + numbers[0] if len(numbers) == 1: if sum_1 == target: count += 1 if sum_2 == target: count += 1 else: dfs(numbers[1:], target, sum_1) dfs(numbers[1:], target, sum_2) def solution(numbers, target): # 2 <= len(numbers) <= 20 global count dfs(numbers, target, 0) return count
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] - 완주하지 못한 선수 (0) | 2021.03.20 |
|---|---|
| [프로그래머스] 단어 변환 (0) | 2021.02.05 |
| [프로그래머스] - 신규 아이디 추천 (0) | 2021.01.25 |
| [프로그래머스] 다리를 지나는 트럭 (0) | 2021.01.05 |
| [프로그래머스] 구명보트 (0) | 2021.01.05 |