본문 바로가기
알고리즘/DFS, BFS

[프로그래머스 - Level 2] 타겟넘버(파이썬)

by 호리미 2022. 1. 11.

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

 

예시 1번 참고 그림