[Python] 프로그래머스_타겟넘버

문제

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

프로그래머스

 

시행착오 코드

 

이 코드는 "틀린"코드입니다.

코드를 구현하면서 백트래킹 방식으로, N과M 풀이법 처럼 리스트에 넣으려는 생각을 먼저 했다.

그래서 numbers의 개수만큼 사용한 것을 종료 조건으로 두고, 그 합의 값이 타겟의 값과 같다면 넣어주는 방식으로 쓰려했다.

하지만 합을 파라미터로 넣어주고, 거기에 리스트도 넣어주는 게 비효율적이었다.

(답도 나오지 않았다)

def solution(numbers, target):
    cnt = 0
    M = len(numbers)
    ans = []
    def dfs(n, nsum, nlst):
        #리스트의 값을 모두 사용했나요?
        if n == M:
            #타겟값과 sum값이 같다면
            if nsum == target:
                ans.append(nlst)
            return
        for i in range(M):
            dfs(n + 1, sum(nlst), nlst + [numbers[i]])
            dfs(n + 1, sum(nlst), nlst + [-numbers[i]])
    dfs(0,0,[])

    answer = len(ans)
    return answer

 

 

해결 코드

 

아직은 타인의 도움이 필요한 병아리(?)기에..머리를 싸매다 원인을 찾았다.

 

1. 리스트로 빼지 않고, 합의 값을 바로 넘겨주어도 된다. (나는 리스트로 만들고, 그 len값을 구하려 했다. 복잡왕 김복잡)

2. 합의 값이 타겟과 같다면 바로 방법의 수로 체크해줘도 된다.

 

dfs와 백트래킹 문제를 몇 개 더 풀어보면서 감을 잡아야 할 것 같다!

 

ans = 0
def solution(numbers, target):
    result = 0
    def dfs(n, result):
        global ans
        # 모든 숫자를 사용했나요?
        if n == len(numbers):
        	# 결과 값이 타겟과 같나요?
            if result == target:
            	# 방법의 수에 추가해주세요
                ans += 1
            return
        # +로 들어가는 것
        dfs(n+1, result + numbers[n])
        # -로 들어가는 것
        dfs(n+1, result - numbers[n])
    
    dfs(0,0)
    answer = ans
    return answer