프로그래머스 - 타겟 넘버

문제 설명

제한사항 및 입출력

풀이

처음 문제를 봤을 때 dp와 dfs가 생각났다. 먼저 dfs 풀이는 각 숫자마다 -, + 두 가지 경우의 수를 모두 탐색하면서 내려가는 경우이다. 내려가면서 남은 모든 수를 더하거나 뺐을 때 목표 숫자가 나오지 않는다면 가지치기해주어서 최적화해줄 수 있다.

내 코드

def solution(numbers, target):
    ans = 0
    
    n = len(numbers)
    # 가지치기를 위한 누적합 배열
    suffix = [0] * (n+1)
    for i in range(n-1, -1, -1):
        suffix[i] = suffix[i+1] + numbers[i]

    def dfs(idx, total):
        nonlocal ans
        
        # 가지치기 조건: 남은 모든 수를 더해도 target 보다 작을 때 혹은 모든 수를 빼도 target 보다 클 때
        if abs(target - total) > suffix[idx]:
            return
        
        # 탈출조건: 배열의 마지막에 도착
        if idx == n:
            if total == target:     # 지금까지 더한 숫자가 target과 같으면 ans += 1
                ans += 1
            return
        
        dfs(idx+1, total + numbers[idx])
        dfs(idx+1, total - numbers[idx])

    dfs(0, 0)
    return ans

 

이렇게 모든 경우의 수를 탐색하면 몇 개가 가능한지 확인할 수 있다.

 

시간 복잡도: 각 원소마다 2가지 부호를 모두 확인하며 진행하므로 O(2^n)이다. n <= 20이므로 최악의 경우에도 약 100만 정도의 크기이기 때문에 무난하게 통과한다. 또한 중간 가지치기로 인해 실제 계산 횟수는 조금? 더 작아질 것이다.

고찰

dp방식의 풀이이다. 가능한 합과 그 개수를 단계별로 누적하여 풀이할 수 있다.

 

dp테이블의 정의는 다음과 같이 내렸다.

dp[i] = i를 만들 수 있는 경우의 수

def solution(numbers, target):
    S = sum(numbers)
    off = S
    
    dp = [0] * (2*S + 1)
    dp[off] = 1
    for i in numbers:
        nxt = [0] * (2*S + 1)
        for s in range(-S, S + 1):
            cnt = dp[s + off]
            if cnt:
                nxt[s + i + off] += cnt
                nxt[s - i + off] += cnt
        dp = nxt
        
    return dp[target + off] if -S <= target <= S else 0

시간 복잡도: O(n * s)이다. s는 모든 수를 더했을 때의 상한으로, 모든 상태공간을 만들어주기 위해 상한값을 구하여 계산해주었다.

 

추가적으로 모든 상태공간을 미리 만들어두지 않고 dictionary를 사용하여 모든 상태공간을 만들지 않고도 풀이할 수 있다.

from collections import Counter

def solution(numbers, target):
    # i: j -> i = 만들 수 있는 값, j = 방법의 수
    dp = Counter({0: 1})
    
    for i in numbers:
        nxt = Counter()
        
        for s, c in dp.items():
            nxt[s+i] += c
            nxt[s-i] += c
        dp = nxt
        
    return dp[target]