코딩테스트/프로그래머스
프로그래머스 level 2 - 타겟넘버 (DFS/BFS)
jhk828
2020. 9. 12. 04:24
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
전역변수 cnt를 DFS() 내에서 사용할 때는 global cnt를 써 줬지만
solution() 내에서 DFS()를 정의해서 변수를 쓸 때는 nonlocal cnt 명시
def solution(numbers, target):
def DFS(L, sum):
if L == len(numbers):
if sum == target:
nonlocal cnt
cnt += 1
else:
DFS(L + 1, sum + numbers[L])
DFS(L + 1, sum - numbers[L])
cnt = 0
DFS(0, 0)
return cnt