[프로그래머스][Python3] 타겟 넘버
2019.11.11 00:26
|
프로그래밍/기타
문제 :
https://programmers.co.kr/learn/courses/30/lessons/43165
나의 풀이 :
def solution(numbers, target):
def dfs(target, remain, visit, end):
if abs(target) <= remain:
if visit == end:
if abs(target) == remain:
nonlocal ans
ans += 1
else:
num = numbers[visit]
dfs(target+num, remain-num, visit+1, end)
dfs(target-num, remain-num, visit+1, end)
numbers = sorted(numbers, reverse=True)
ans = 0
dfs(target, sum(numbers), 0, len(numbers)-1)
return ans
한마디 :
모든 경우의 수를 탐색하기에 앞서 가지치기를 위해 역순 정렬을 먼저 해두었다. 큰 수부터 먼저 처리를 해야 나머지 경로를 추가 탐색할 가치가 있는지 빠르게 판단할 수 있다.
'프로그래밍 > 기타' 카테고리의 다른 글
| [프로그래머스][Python3] 타겟 넘버 (0) | 2019.11.11 |
|---|---|
| [Python3][2020카카오공채] 가사 검색 (0) | 2019.10.07 |
| [Python3][2020카카오공채] 괄호 변환 (0) | 2019.10.04 |
| [Python3][2020카카오공채] 문자열 압축 (0) | 2019.10.03 |
| [Python] json.dumps 한글 유니코드 (0) | 2019.04.05 |
| 하노이의 탑 (0) | 2019.02.13 |
| [Python3] 카카오 코드 페스티벌 2018 예선 - 인형들 (0) | 2019.01.18 |
| python-ldap Windows Active Directory unicodePwd userAccountControl DSID-031A120C (0) | 2018.12.20 |
| 티스토리 블로그 SSL(TLS) www <-> non-www 상호 전환 Javascript (6) | 2018.09.08 |
