회고/알고리즘
[프로그래머스 / Lv 2] 타겟 넘버
마코maco
2023. 9. 5. 23:37
https://school.programmers.co.kr/learn/courses/30/lessons/43165
[프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr](https://school.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 이하인 자연수입니다.
접근
- 입력받은 숫자 배열의 각 요소에 +1을 곱하거나 -1을 곱해서 모두 더한 값이 target인 경우의 수를 센다.
- 함수에서 각 dfs 스텝마다 1 또는 -1을 담은 operation 리스트를 add한다.
- 함수에서 base case를 operation size가 숫자 배열이 됐을 때로 설정하고 이때, operation의 모든 값을 각 숫자 배열 요소에 곱해서 모두 더한 값이 target과 일치하면 횟수를 센다.
- 함수마다 +1을 담은 dfs를 재귀 호출하고 -1을 담은 dfs를 재귀 호출하여 하나의 함수에서 총 두 가지 경우에 대해 재귀 호출한다.
- 모든 횟수를 더하면 끝.