https://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
<내 코드>
- 주어진 수를 계속 더하거나 빼면서 target 넘버가 되는지 확인하는 문제 -> 깊이우선탐색 -> DFS
- 아래 트리는 target이 3이 될때만 표현했다.(다 그리기엔 공간이 부족해서,,)
- 백준에서 전형적인 문제만 풀다가 새로운 느낌이라 머리가 아픔 ㅠ
import sys
sys.setrecursionlimit(10**9)
def solution(numbers, target):
n = len(numbers)
def dfs(idx, start):
global answer
if idx==n: #가장 아래까지 탐색 다 했을 때
if start == target: #최종적으로 target이 만들어졌으면
answer+=1
return answer
else:
dfs(idx+1, start + numbers[idx])
dfs(idx+1, start - numbers[idx])
global answer
answer = 0
dfs(0,0)
return answer
'알고리즘 > DFS, BFS' 카테고리의 다른 글
[백준-실버1] 1697 숨바꼭질(파이썬, BFS) (0) | 2022.01.13 |
---|---|
[백준-실버1] 7576 토마토(파이썬 , BFS) (0) | 2022.01.13 |
[백준-실버1] 1743번 음식물 피하기(파이썬, DFS 풀이) (0) | 2022.01.06 |
[백준-실버2] 11725번 트리의 부모 찾기(파이썬, DFS 풀이) (0) | 2022.01.06 |
[백준-실버2] 2644번 촌수계산(파이썬, DFS 풀이) (0) | 2022.01.05 |