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

문제 링크 >> 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+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

 

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

 

👉 입출력

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

 

 

📝 풀이

def solution(numbers, target):
  answer = 0
  n = len(numbers)
  
  def dfs(idx, result):
    nonlocal answer

    if idx == n:
      if result == target:
        answer += 1
      return
    else:
      dfs(idx+1, result + numbers[idx])
      dfs(idx+1, result-numbers[idx])
  
  dfs(0, 0)
  return answer

 

이 문제는 하루를 꼬박 생각했지만 어떻게 풀지 감조차 오지 않아 해설을 참고했다.

(진짜 풀고 싶었는데 결국 졌다...)

 

아무튼 결론부터 얘기하자면 결국 다음 인덱스의 수를 빼보고 더해보는 두 가지의 경우의 수로 계속 갈라가며 target이 나올 때를 찾는 거였다.

이 찾는 과정을 깊이 탐색하는 dfs로 푼 것이고.

이 과정을 그림으로 살펴보면 다음과 같다.

 

 

dfs에서 일단 깊이가 numbers의 길이와 같을 때까지 탐색한다.

이 과정은 numbers의 모든 수를 이용해 적절히 더하거나 빼서 타겟 넘버를 만들어야 하기 때문이다.

 

깊이가 numbers의 길이와 같다면 계산된 결과가 타겟 넘버와 같은지 살펴보고 같다면 answer += 1을 해준다.

깊이가 numbers의 길이와 같지 않다면 아직 살펴볼 수가 남았다는 뜻이다.

따라서 해당 인덱스의 값을 더하고 빼는 두 가지 경우의 수로 나누어 살펴본다.

 

결국 answer에는 numbers의 요소를 적절히 더하거나 빼서 타겟 넘버를 만든 경우의 수만 남게 되고 이를 리턴해준다.

 

 

다른 풀이를 살펴보다 이게 재귀함수다! 하는 풀이가 있어 가져와봤다.

 

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

 

역시 재귀함수는 몇 번을 봐도 어렵다.

 

 

🔍 참조

타겟넘버 https://velog.io/@ju_h2/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2-%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84-BFSDFS