[Algo Rhythm🕺💃]
난이도: Level 2
1. 문제
| 문제 설명
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 이하인 자연수입니다.
| 입출력 예
2. 알고리즘 by Yoon
이 문제는 DFS의 가장 대표적인 문제라 할 수 있는데, 우선 위 그림을 예시로 들어 알고리즘을 설명하도록 하겠다.
- input 값으로 들어오는 numbers의 배열 길이만큼 level의 높아진다.
- 시작점(start)을 기준으로 +일 수도 있고, -일 수도 있기 때문에 두 갈래 left와 right로 나뉘어 DFS가 적용된다.
- 재귀(recursion) 함수가 사용된다.
-
우선 dfs라는 함수를 호출할 때 인자 값으로는 numbers의 배열, target, 그리고 추가적으로 level 값(level)과 해당 레벨까지의 원소 합(sum)이 필요하다. 따라서, 처음에는 level이 0이고 sum도 0이므로 dfs(numbers, target, 0, 0)으로 시작한다.
-
경우의 수는 +와 -이므로 level을 증가시키는 동시에 (지금까지 누적된 sum + level까지의 원소 합인 numbers[level])를 인자로 수정하여 dfs를 다시 호출한다.
-
recursion을 종료시키는 조건문으로는 level이 numbers 배열의 길이와 동일해 졌을 때 모든 원소의 경우의 수를 다 보았다는 뜻이므로 해당 조건문에 따라 값을 return 해준다.
3.1 이때 sum이 목표로 하는 target 값과 일치하면 1을 return 한다.
3.2 그렇지 않으면 0을 return 한다. -
그렇게 조건에 맞는 target과 sum이 동일한 경우에만 return 했던 1의 값이 누적되면서 answer가 증가한다.
최종적으로는 문제에서 주어진 예제에 대해 아래와 같이 그릴 수 있고, 빨간 동그라미가 답이 된다!
3. 소스코드
class Solution {
public int solution(int[] numbers, int target) {
return dfs(numbers, target, 0, 0);
}
public int dfs(int[] numbers, int target, int level, int sum){
// 배열 길이만큼 level이 증가하고, 각 원소들의 합이 target과 동일한 경우
if(level == numbers.length){
if(target == sum) return 1;
else return 0;
}
// left // right
return dfs(numbers, target, level+1, sum + numbers[level])+ dfs(numbers, target, level+1, sum - numbers[level]);
}
}4. 느낀점
문제를 읽자마자 DFS라는 것은 한 번에 파악 되었고, DFS의 대표적인 문제라고 생각했다.recursion이기 때문에 바로바로 떠오르지는 않았지만, dfs함수를 호출할 때마다 달라져야 하는 값과 recursion을 끝내야 하는 조건들을 생각해보니 금방 해결할 수 있었다. 그리고 무엇보다 소름이었던 건 내가 짠 코드가 프로그래머스 '다른 사람의 풀이'에서 인기 순위가 높은 코드와 동일했다. 조금 많이 뿌듯했다!!! @'-'@
