2/프로그래머스
프로그래머스 연습 문제 - 타겟 넘버
하례은
2020. 9. 18. 13:30
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/BFS 문제
def dfs(number, index, numbers, target):
sm = 0
if len(numbers) == index:
if target == number:
return 1
return 0
sm += dfs(number + numbers[index], index+1, numbers, target)
sm += dfs(number - numbers[index], index+1, numbers, target)
return sm
def solution(numbers, target):
answer = 0
answer += dfs(numbers[0], 1, numbers, target)
answer += dfs(-numbers[0], 1, numbers, target)
return answer
재귀함수와 DFS를 사용하였다. 사실 정말 모르겠어서 고민하다가 다른사람 풀이를 참고하여 풀었다... 오늘도 하나 배워간다...