프로그래머스 lv2 [타겟 넘버] C++, python - bfs/dfs

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

 

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers                                                                                                   target                return

[1, 1, 1, 1, 1]

3

5

 

1. c++

 

dfs를 인덱스로도 활용할 수 있다는 사실을 알았다.

count와 sum 변수를 이용하고 인덱스마다 +, - 두가지 경우를 모두 고려할 수 있도록 dfs를 두개 만들어 주면 된다.

어떤 블로그에서 count+1을 count++로 바꾸면 에러가 난다는 것을 보았는데, 이는 count++로 하면 밑의 dfs에서 이미 바뀐 count값으로 반영되기 때문에 그렇다고 한다.

 

2. python

 

• super = sub

하나의 노드에 대한 탐색이 끝나면 반복이 끝나서 sub에서 계산한 값을  super로 덮어둔다. 

(super 1개 => sub 2개, super 2개 => sub 4개.....)

 

• super.count(target)

리스트에서 특정 값의 개수를 구하는 함수. target과 같은 값의 개수를 찾아준다.