[프로그래머스 lv 2] 타겟 넘버

사용 언어 - Python3

문제 - 타겟 넘버

프로그래머스

 

 

정답

DFS 문제 (정답 맞춘 여부 X)

정답1 풀이 - dfs 문제

1. answer = 0 정답개수 세는 변수

 

2. dfs 인자 정의

depth = 사용한 숫자개수. 왼쪽숫자부터 한개씩 꺼내서 연산한다. 0에서 시작해서 len(numbers)가 될때까지 반복

numbers = 리스트형태의 input값

target = 숫자형태의 input값

total = 값을 계산한 결과. total이 target과 같다면 정답개수에 추가해준다.

 

3. 재귀적으로 반복

dfs를 한번 할때마다 depth +1로 바꿔준다. total값에서 해당 숫자를 더하거나 빼준다.

 

4. solution 함수에서 dfs 시작지점 설정

dfs(0,numbers,target,0)

# dfs 이용
answer = 0
def dfs(depth, numbers, target, total):
    global answer
    N = len(numbers)
    if(depth== N and target == total):
        answer += 1
        return
    if(depth == N):
        return

    dfs(depth+1,numbers,target,total+numbers[depth])
    dfs(depth+1,numbers,target,total-numbers[depth])
    
def solution(numbers, target):
    global answer
    dfs(0,numbers,target,0)
    return answer

 

정답2 풀이 - 재귀

1. 예외를 처리한다.

numbers가 없고 target은 0인 경우, 경우의 수는 단 한가지이기 때문에 1을 return한다.

numbers만 없는 경우, 경우의 수는 0이므로 0을 return한다.

 

2. numbers를 왼쪽 앞부터 target - (numbers 계산값)  == 0이 될때까지 재귀적으로 반복한다.(?)

target - numbers[0] +solution(numbers[1:], target+numbers[0])

# 재귀함수 이용
def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

 

문제가 백준 14888번과 유사합니다.

14888번: 연산자 끼워넣기

 

---

레퍼런스

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부