[PG/Python] 타겟 넘버

📌 문제

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

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

 

📌 문제 접근 방법

1. 문제 분류가 dfs, bfs길래 그걸 어떻게 써야하나 한참 고민하다가 아이디어가 안떠올라서 그냥 일단 해보자! 하고 짜봤다. (사실 시간초과 나려나 했는데 안나서 읭?했음..)
2. 숫자의 개수보다 1개 더 많게 리스트를 만들어주고 반복문을 돌리면서 리스트 안의 모든 값에 숫자를 더하고 빼서 다음 번째 리스트에 넣어주었다.
3. 맨 마지막에 있는 리스트에서 타겟 넘버의 개수를 세서 출력!

 

📌 코드

# 프로그래머스 타겟 넘버

def solution(numbers, target):
    temp = [[] for _ in range(len(numbers)+1)]
    temp[0].append(0)

    for i in range(len(numbers)):
        for num in temp[i]:
            temp[i+1].append(num-numbers[i])
            temp[i+1].append(num+numbers[i])
    
    answer = temp[-1].count(target)
    return answer

print(solution([1, 1, 1, 1, 1], 3), 5)
print(solution([1, 2, 1, 2], 2), 3)
print(solution([1, 2, 1, 2], 6), 1)