프로그래머스 / 백트래킹 / 타겟 넘버

문제

---

 

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

프로그래머스

 

입출력

---

 

 

해설

---

 

N개의 음이 아닌 정수가 있을 때, 각 숫자를 더하거나 빼서 Target을 만들 수 있는 방법 수를 알아내는 문제이다.

 

주어지는 숫자는 총 20개로 경우의 수를 생각해봤을 때 각각의 숫자들은 더하거나 빼는 경우밖에 없다.

즉, 2^20의 경우의 수가 나오게 된다. 해당하는 숫자는 1,048,576으로 굉장히 작은 숫자이며 모든 경우를 탐색해도 풀릴 것이라고 생각했다.

 

그래서 백트래킹을 이용하여 경우의수 탐색을 해주었다.

 

detph 깊이와 total을 지정하여 현재 얼만큼의 숫자를 더하거나 빼주었는지 체크해주었고 모든 숫자를 더하거나, 빼주었을 때 target과 동일한지 체크하여 answer에 증가하도록 해주었다.

 

정답코드

---

'''
'25. 09. 24.(수)

1. n개의 음이 아닌 정수가 있음.
2. 적절히 더하거나 빼서 타겟 넘버를 만들려고 함.

2^20의 경우의 수가 있음.
backtracking으로 풀이를 진행하면 됨.

'''
answer = 0
def backtracking(depth: int, numbers: list, target: int, total: int) -> None:
    global answer
    #depth == numbers가 되면 종료
    if depth == len(numbers):
        #내가 찾으려는 숫자와 동일하면 1 증가
        if total == target: answer += 1
        return
    #현재 depth에 있는 number를 더하거나 뺄 수 있음.
    backtracking(depth + 1, numbers, target, total + numbers[depth])
    backtracking(depth + 1, numbers, target, total - numbers[depth])
    
    
def solution(numbers, target):
    global answer
    backtracking(0, numbers, target, 0)
    return answer

 

깃허브 : https://buly.kr/4biirZK

유튜브 : https://youtu.be/qzNOb2xM80g