Coding Test/programmers

[프로그래머스] 타겟 넘버 - python (레벨 2)

조용장 2022. 4. 10. 09:44

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

 

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

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수

programmers.co.kr

풀이

문제를 보았을때 알수있는 힌트

숫자 마다 +,- 를 반복해서 계산하고 마지막은 target과 맞는지 확인하면 되는 문제다.

반복적으로 모든 넘버를 계산하기에 DFS로 풀면 쉽게 풀릴듯했다.

 

def dfs(number,count,num_sum,result):
    if len(number)==count:
        result.append(num_sum)
    else:
        dfs(number,count+1,num_sum+number[count],result)
        dfs(number,count+1,num_sum-number[count],result)
    
def solution(numbers, target):
    answer = 0
    result=[]
    num_sum=0
    dfs(numbers,0,0,result)
    # print(result)
    # print(result.count(target))
    answer=result.count(target)
    
    return answer

https://github.com/dydwkd486/coding_test/blob/main/programmers/타겟넘버.py 

 

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리

코딩테스트 공부한 내용 정리. Contribute to dydwkd486/coding_test development by creating an account on GitHub.

github.com