https://programmers.co.kr/learn/courses/30/lessons/43165
코딩테스트 연습 - 타겟 넘버
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수
programmers.co.kr
깊이/너비 우선 탐색 유형에 있는 문제이다.
문제를 보면 4 1 2 1 에서 +4,-4, +1-1, +2-2, +1-1을 모두 탐색해야 하므로
완전 탐색으로 살펴봐야 한다는 것은 알겠다.
여기서 조합을 어떻게 해야하냐가 문제인데
이렇게 풀었다......
코드
class Solution {
public static int answer = 0;
public int solution(int[] numbers, int target) {
dfs(numbers, target, 0, 0);
return answer;
}
public void dfs(int[] numbers, int target, int count, int sum){
if(count == numbers.length){
if(target == sum)
answer++;
}
else{
dfs(numbers, target, count + 1, sum + numbers[count]);
dfs(numbers, target, count + 1, sum - numbers[count]);
}
}
}
어렵다...
남의 코드를 살펴보자
비슷하게 풀었다. 함수를 int return 하게 해서 answer++ 안하고 그냥 return 1을함
음~ sum + number[count] 랑 - 랑 더하는 이유는 어차피 return 1 or 0 된거 더해야하니까?
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 소수 찾기 for JAVA _ 완전 탐색 알고리즘 + 순열, 소수찾기 (0) | 2022.02.13 |
|---|---|
| [프로그래머스] 모의고사 for JAVA _ 완전탐색 알고리즘 (0) | 2022.02.11 |
| [프로그래머스] 구명보트 for JAVA _ 그리디 알고리즘 (0) | 2022.01.04 |
| [프로그래머스] 큰 수 만들기 for JAVA _ 그리디 알고리즘 (0) | 2022.01.04 |
| [프로그래머스] 조이스틱 for JAVA _ 그리디 알고리즘 (0) | 2022.01.03 |