사용자 도구

사이트 도구


ps:problems:programmers:43165

타겟 넘버

ps
링크https://programmers.co.kr/learn/courses/30/lessons/43165
출처프로그래머스
문제 번호43165
문제명타겟 넘버
레벨Level 2
분류

DP

시간복잡도O(n*n*m)
인풋사이즈n<=20, m<=50
사용한 언어Python
해결날짜2020/11/23
  • Subset sum 문제처럼, 각 숫자의 크기 제한이 없다면 NP가 되는 문제이지만, 제한이 있어서 DP로 풀 수 있다.
    • 왜 사이트에서는 BFS/DFS로 분류되어 있는지 모르겠다.

풀이

  • DP[n][t]을 numbers[0]부터 numbers[n-1]까지를 써서 합이 t가 되는 경우의 수라고 하면
    • DP[n][t] = DP[n-1][t-numbers[n]] + DP[n-1][t+numbers[n]] 이 된다.
  • m을 가능한 숫자의 최대값(=50) 이라 하면, n개의 숫자의 합은 [-n*m, n*m] 범위에 있으니까, DP 테이블의 크기는 n*(2*n*m)으로 잡아서 처리하면 된다. 이렇게 되면 테이블 한칸을 채우는데 O(1)이니까 총 시간 복잡도는 O(n*n*m).
  • 실제 구현할 때는, 테이블 전체를 유지할 필요 없이 최근 2행만 유지하면서 업데이트하면 된다.
  • 또한 DP[n-1][t]가 0이 아닌 곳에서만 DP[n][t±numbers[n]]를 업데이트 해주면 되고, DP[n-1][t]가 0이 아닌 곳의 갯수는 2*n*m에 비해서 많이 적기 때문에, 배열 대신에 set을 쓰는 것이 유리하다.
  • 숫자의 갯수가 최대 20개라서, O(2^n)으로 완전 탐색을 해도 풀이는 가능하다..

코드

"""Solution code for "Programmers 43165. 타겟 넘버".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/43165
- Solution link: http://www.teferi.net/ps/problems/programmers/43165
"""

import collections


def solution(numbers, target):
    dp_cur = {0: 1}
    for number in numbers:
        dp_cur, dp_prev = collections.defaultdict(int), dp_cur
        for result, count in dp_prev.items():
            dp_cur[result + number] += count
            dp_cur[result - number] += count
    return dp_cur[target]

토론

댓글을 입력하세요:
Q V M E K
 
ps/problems/programmers/43165.txt · 마지막으로 수정됨: 2021/01/21 16:31 저자 teferi