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
'Coding Test > programmers' 카테고리의 다른 글
[프로그래머스] 등굣길 - python (레벨 3) (0) | 2022.05.29 |
---|---|
[프로그래머스] 정수 삼각형 - python (레벨 3) (0) | 2022.05.13 |
[프로그래머스] 가장 큰 정사각형 찾기 - python (레벨 2) (0) | 2022.05.13 |
[프로그래머스] 오픈채팅방 - python (레벨 2) (0) | 2022.04.04 |
[프로그래머스] 다단계 칫솔 판매 - python (레벨 3) (0) | 2022.04.01 |