[프로그래머스 - Python] 타겟 넘버

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

문제 요약

n개의 음이 아닌 정수들 순서 바꾸지 말고 적절히 + - 하여 타겟 넘버 만들기
만들 수 있는 방법의 수 구하기

 

코드 설명

cnt = 0
def dfs(numbers, target, current, depth):
    global cnt
    if depth == len(numbers):
        if current == target:
            cnt += 1
        return
    
    dfs(numbers, target, current + numbers[depth], depth + 1)
    dfs(numbers, target, current - numbers[depth], depth + 1)

def solution(numbers, target):
    dfs(numbers, target, 0, 0)# 현재 깊이까지 계산된 값, 현재 깊이
    return cnt

 

문제를 읽고 dfs 유형임을 파악하는 것은 어렵지 않다

 

깊이 변수를 하나씩 늘려가주면서 dfs로 재귀 탐색을 해준다.

+, - 두 가지 연산이 가능함으로 dfs를 각각 돌려준다.

 

모든 숫자들을 연산하였을 때,

타겟 넘버와 일치하는지 확인하고

일치하는 경우 카운팅을 세어준다.

 

카운팅 변수를 전역 처리해서 반환될 수 있도록 해준다.

 

다른 풀이

def solution(numbers, target):
    dfs(numbers, target, 0, 0)# 현재 깊이까지 계산된 값, 현재 깊이
    return cnt

def DFS(numbers, target, depth):
    answer = 0
    if depth == len(numbers):
        if sum(numbers) == target:
            return 1
        else:
            return 0
        
    else:
        answer += DFS(numbers, target, depth+1)
        numbers[depth] *= -1
        answer += DFS(numbers, target, depth+1)
    return answer

 

numbers 자체에 음수 부호 곱셈으로 값을 변경하고 sum 함수를 사용해서 조건식에서 결과값을 타겟 넘버와 비교하는 방식

전역변수를 사용하지 않고 지역 변수에 값을 담아서 반환하는 방식

 

 

배운 점

- 지역변수로 카운팅 할 때와 전역변수로 카운팅 할 때의 dfs return 형태를 눈여겨서 보자

 

참고 자료

https://dmaolon00.tistory.com/entry/ProgrammersPython-%ED%83%80%EA%B2%9F-%EB%84%98%EB%B2%84-DFSBFS