Programmers, 백트레킹, ‘타겟넘버’

프로그래머스 연습문제 중 43165번 ‘타겟넘버’

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 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4 + 총 2가지 방법이 있으므로, 2를 return 합니다.

---

풀이

가능한 모든 경우를 탐색하며 target와 같다면 탐색을 종료하는 백트래킹 문제이다. 주어지는 입력 number의 원소의 개수와 가질 수 있는 부호의 개수가 같다.
단 이 문제에서 주의 해야 할 부분은 target을 만족하는 경우의 순서는 고려하지 않으므로 조합인 combinations을 고려해야한다.

간단하게 itertools 모듈의 combinations을 쓰는게 동작도 가장 빠르고 간단하지만 실전에 대비해 직접 조합을 구하는 dfs를 구현 해보았다. dfs로 구현하는 조합은 이전에 다뤄봤던 N과 M(2)을 조금 수정했다.

[1, 2, 3, 4] 중 2개를 뽑는 조합을 구한다고 해보자. 그러면 보통 다음과 같이 경우를 따진다.

• 1로 시작하는 경우
  • [1, 2]
  • [1, 3]
  • [1, 4]
• 2로 시작하는 경우
  • [2, 3]
  • [2, 4]
• 3으로 시작하는 경우
  • [3, 4]

이 과정을 [] 를 부모노드로 갖고, [1, 2, 3, 4]를 자식노드로 하며, 방문하는 순서를 고려하지 않는 탐색을 한다고 생각 할 수 있다.

이를 코드로 구현하면 다음과 같다.

def solution(numbers, target):
    n = len(numbers)
    cnt = 0

     # 방문여부 확인을 위한 배열 선언
    visited = [False] * n

    def dfs(depth, idx):

        nonlocal cnt

         # depth가 n과 같다면 탐색 종료
        if depth == n:
            return

         # 지금까지 탐색 중 numbers의 합이 target 과 같다면 cnt를 증가시키고 탐색 종료
        if sum(numbers) == target:
            print(numbers)
            cnt += 1
            return

         # 입력받은 idx 부터 n까지 재귀적으로 dfs 진행
        for i in range(idx, n):
            if not visited[i]:
                visited[i] = True
                 # 탐색한 인덱스의 numbers 값의 부호를 -1로 바꿔줌
                numbers[i] *= -1
                dfs(depth + 1, i + 1)
                visited[i] = False
                numbers[i] *= -1
    dfs(0, 0)
    return cnt

solution([4, 1, 2, 1], 4)

[4, -1, 2, -1]
[4, 1, -2, 1]





2