문제풀이는 여기서!
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 이하인 자연수입니다.
입출력 예
numberstargetreturn[1, 1, 1, 1, 1] | 3 | 5 |
[4, 1, 2, 1] | 4 | 2 |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
+4+1-2+1 = 4
+4-1+2-1 = 4
- 총 2가지 방법이 있으므로, 2를 return 합니다.
문제해결 keyPoint
- 주어진 숫자의 개수는 2개 이상 20개 이하다. -> 범위가 매우적어 완전탐색을 생각 할수있다.
- 완전탐색을 할때 DFS,BFS 등이 있고, 각 알고리즘에 따른 사용법을 확인하자.
- 사실 아직 잘 모르겠다. 아침이라 머리가 안돌아가는듯..
20220914 1차시도
음.. 솔직히 보자마자 뭔소리인지 모르겠다. 아침이라 그런걸수도 있지만, 모르겠다. ㅎ
그리고 처음부터 DFS/BFS로 적혀있어서... 모르는걸 알지만 그래서 풀어보기로 한것도 있다.
BFS,DFS 설명을 봐도 이 문제에는 어떻게 적용하는건지 이해가 되지 않는다! ㅎㅎㅎ 30분만 뻐기면 어차피 풀이를 본다!! 귀찮아도 좀만 더 생각해보자.
왜?? BFS가 아니고 DFS로 풀었을까?... 사실 BFS로 하기엔 내가봐도 뭔가 안맞는것 같다. 순서를 바꿀수 없으므로 무조건 루트노드(배열의 첫번째 원소) 부터 리프노드까지(배열의 마지막 원소) 순회해야 한다.
단순 완전탐색으로도 풀수 있겠지만, 그러면 너무 알고리즘이 복잡하다. 그래서 재귀형식으로 푸는것 같다. = DFS
class Solution {
static int count = 0;
public int solution(int[] numbers, int target) {
int answer = 0;
this.dfs(0,numbers,target,0);
answer=count;
return answer;
}
public void dfs(int index, int[] numbers, int target, int sum){
//배열의 끝까지 돌았다면 누적 합계를 확인한다.
if(index == numbers.length) {
if (sum == target) {
count++;
}
return;
}
//더하는 경우, 빼는 경우 모두를 확인해야 한다,(완전탐색)
dfs(index+1, numbers,target,sum+numbers[index]); //더하는 경우
dfs(index+1, numbers,target,sum-numbers[index]); //빼는 경우
}
}
refs
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
https://dding9code.tistory.com/9
'알고리즘' 카테고리의 다른 글
프로그래머스[17677] - 뉴스 클러스터링(lv2) (0) | 2022.09.16 |
---|---|
프로그래머스[1292] - 숫자의 표현 (lv2) (0) | 2022.09.15 |
프로그래머스[12909] - 올바른 괄호(lv2) (0) | 2022.09.14 |
프로그래머스[12914] - 멀리 뛰기(lv2) (0) | 2022.09.12 |
프로그래머스[12941] - 최솟값 만들기(lv2) (0) | 2022.09.12 |