[DFS/BFS] 타겟넘버

문제링크

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

 

해설

내 풀이

간단하게 내가 이 문제를 직접 풀면 어떻게 풀까 고민하다가 생각난 풀이이다.

1. 숫자가 여러개 들어있을 때 값을 빼줄지 더해줄지에 대한 모든 경우의 수를 미리 짜두고
2. 이에 대한 계산을 진행하는 코드이다

나는 이를 구현하기 위해서 생각 났던 방식이 어짜피 더하기 빼기는 결국 -1, 1을 곱해서 더하는 과정이라고 생각했고, 이를 구현하기 위해 이진법으로 2의 숫자의 갯수 제곱만큼 늘려주고 이렇게 부여된 값을 각각 숫자에 더해주는 과정으로 진행했다

 

예를 들어서 문제에 나온 것 처럼 예를 들어 [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

이를 한 번에 제시하기 위해서

00000
00001
00010
00011
00100
00101
...

 

이런식으로 모든 가짓수를 만들고 반복문을 통해 $(-1)^i$와 해당 숫자를 곱하면

$(-1)^0$은 1이고 $(-1)^1$은 -1이므로 원하는 값으로 잘 나온다.

이를 모두 더해주고 값이 target과 같다면 answer 값을 1개 추가해준다 

 

이를 구현한 코드는 다음과 같다

def solution(numbers, target):
	answer = 0    
    l = len(numbers)

    for n in range(2**l):
        k = format(n, 'b')
        c = str(k).zfill(l)
        r = 0
        for i, num in enumerate(numbers):
            r += (-1)**(int(c[i])) * num

        if r == target:
            answer += 1
    
    return answer

 

 

DFS를 이용한 풀이

def solution(numbers, target):
    global answer

    answer = 0
    def dfs(idx, total):
        global answer

        # 마지막 인덱스 도달했을 때 값이 원하는 숫자가 맞는지 확인
        if (idx == len(numbers)):
            if total == target:
                answer += 1
            return
        
        # 모든 가짓수 계산해준다 (더하기, 빼기)
        dfs(idx + 1, total + numbers[idx])    
        dfs(idx + 1, total - numbers[idx])
        
        return
    
    dfs(0,0)
    return answer

 

• 이렇게 계산하면 numbers의 갯수만큼 이동하면서 모든 가짓수를 다 셀 수 있게 된다

 

def solution(numbers, target):
    idx = curr = 0

    def dfs(nums, target, curr, idx):
        # 결과 비교는 마지막에 인덱스가 끝까지 갔을 때 합니다
        if idx == len(nums):
            return 1 if curr == target else 0

        # idx를 한칸 움직여주고 curr에 이번 값을 더하거나 뺍니다
        return dfs(nums, target, curr + nums[idx], idx + 1) \
                + dfs(nums, target, curr - nums[idx], idx + 1)

    answer = dfs(numbers, target, idx, curr)
    return answer

 

• 이 코드는 한번에 이 값이 타겟 값인지 확인한다는 점에서 좋은 코드인 것 같다.

 

총평/느낀점

• 이 문제는 프로그래머스내에서 DFS/BFS 카테고리 안에 있어서 풀었는데 도저히 DFS로 푸는 방법을 떠올리지 못했던 문제이다
• 이런식으로 사고하는 연습을 해보는 것도 많은 도움이 되는 것 같다

 

출처

• 프로그래머스 Yunie님, plsletmecreateusername@gmail.com님 코드 참고