[프로그래머스] 타겟 넘버/DFS/파이썬 (어렵)

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=python

프로그래머스

 

1. DFS사용 시 => (이해못함)

# answer : 경우의 수
answer = 0

# idx: 배열의 숫자를 선택할 index, cur: 차례대로 계산 중인 결과 값
def dfs(idx, cur, numbers, target):
    global answer
    
    if idx == len(numbers):
        if cur == target:
            answer += 1
        return 0
        
    dfs(idx+1, cur+numbers[idx],numbers, target)
    dfs(idx+1, cur-numbers[idx],numbers, target)


def solution(numbers, target):
    
    dfs(0,0,numbers, target)
    
    return answer

 

문제풀이

 

1. numbers 배열의 각 숫자마다 +와 - 사용한 모든 계산 수행하기 위해 재귀함수 활용한 DFS 구현

dfs(idx+1, cur+numbers[idx], numbers, target)

dfs(idx+1, cur-numbers[idx], numbers, target)

 

2. 재귀함수 호출할 때마다 index 1증가

 

3. 현재까지 계산 결과가 target과 같으면 answer +1

 

 

 

 

참고

 

https://moseory20.tistory.com/29

프로그래머스(DFS/BFS)-타겟 넘버-Python

 

 

 

2. product로 조합 생성해서 풀기

 

from itertools import product
def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l)))
    return s.count(target)

 

풀이

 

1. 가능한 조합의 갯수가 많지 않으니 product 조합 가능

2. (x, -x) 의 모든 가능한 조합 생성 후 s 리스트에 모든 조합의 합 추가

3. target 값과 s리스트 값중 같은 값의 갯수 세서 리턴

 

 

3. 숫자 조합 생성

 

l = [(x, -x) for x in numbers]

• numbers의 각 숫자 x에 대해 (x, -x) 형태의 튜플을 생성합니다.
• 예: numbers = [1, 2]라면, l = [(1, -1), (2, -2)]

---

4. 모든 조합의 합 계산

 

s = list(map(sum, product(*l)))

• product(*l)는 l에서 모든 가능한 조합을 생성합니다.
  • 예: l = [(1, -1), (2, -2)]라면, product(*l)는 [(1, 2), (1, -2), (-1, 2), (-1, -2)]를 만듭니다.
• 각 조합의 합을 계산하고, 이를 리스트 s에 저장합니다.

---

5. 목표값과 같은 경우의 수 계산

 

return s.count(target)

• 리스트 s에서 target 값과 같은 요소의 개수를 세어 반환합니다.

---

예시 실행

 

numbers = [1, 1, 1, 1, 1] target = 3 print(solution(numbers, target))

1. l 생성:
2.  
   l = [(1, -1), (1, -1), (1, -1), (1, -1), (1, -1)]
3. 모든 조합 생성 및 합 계산:
4.  
   product(*l) = [ (1, 1, 1, 1, 1), (1, 1, 1, 1, -1), ..., (-1, -1, -1, -1, -1) ] s = [5, 3, 3, 1, ...] # 각 조합의 합
5. 목표값 3의 개수 계산:
6. 
   
   s.count(3) = 5

결과:

5

 

 

 

---

 

참고

 

https://ror-coding.tistory.com/104

[Programmers] 타겟 넘버 - 43165