[프로그래머스] 타겟넘버 (파이썬)

문제 링크

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

코딩테스트 연습 - 타겟 넘버

 

문제 풀이

이 문제는 재귀를 이용한 완전탐색으로 쉽게 해결할 수 있다.

숫자 앞에 + 나 - 둘 중 1개가 올 수 있으므로, 총 만들수 있는 경우의 수는 2^n 이다.

즉 Big(O) = 2^n 이다.

문제에서 n 의 범위가 20 이하라고 했으므로( 백만번 계산 ), 시간초과는 절대 안걸린다.

 

시간 복잡도

Big(O) = 2^n

소스 코드

cnt = 0;

def solution(numbers, target):
    n = len(numbers);
    
    
    def rec(answer, order):
        global cnt;
        if order >= len(numbers):
            if answer == target:
                cnt += 1;
            return ;
        rec(answer + numbers[order], order + 1);
        rec(answer - numbers[order], order + 1);
    
    rec(-numbers[0], 1);
    rec(numbers[0], 1);
    
    return cnt;