반응형
https://school.programmers.co.kr/learn/courses/30/lessons/43165
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이
주어진 숫자들로 덧셈과 뺄셈만을 이용해서 목표값을 만드는 문제이다.
모든 경우의 수를 거쳐야하므로 깊이 우선 탐색 (dfs)가 바로 생각이 났다. dfs 함수를 생성하고 마지막 노드까지 탐색했을 때 목표값과 일치한다면 answer++를 해주는 방식으로 코드를 설계했다.
여기서 중요한 건 목표값을 도달했을 때 answer++를 해주는 것이 아닌 마지막 노드까지 탐색을 완료해야한다는 점이다.
깊이 우선 탐색 (dfs)를 잘 모르는 경우 아래를 참고해주면 좋다.
[JAVA] 깊이 우선 탐색 DFS 개념과 작동 방식
금일 프로그래머스에서 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 관련 알고리즘 문제를 풀다가 막혀버린 두부입니다. 이렇게 쉬워보이는 알고리즘도 못 푸니까 스스로에게 화가 나네요. 잡담은
sookr5416.tistory.com
class Solution {
int answer = 0;
public int solution(int[] numbers, int target) {
dfs(numbers, 0, target, 0);
return answer;
}
public void dfs(int[] numbers, int idx, int target, int sum) {
if (idx == numbers.length) {
if (sum == target) answer++;
return;
}
dfs(numbers, idx+1, target, sum + numbers[idx]);
dfs(numbers, idx+1, target, sum - numbers[idx]);
}
}
반응형
'알고리즘 > DFS & BFS' 카테고리의 다른 글
[백준]JAVA - 7576번: 토마토 (0) | 2022.10.07 |
---|---|
[백준]JAVA - 2178번: 미로탐색 (0) | 2022.10.05 |
[백준]JAVA - 1697번: 숨바꼭질 (0) | 2022.09.28 |
[백준]JAVA - 2667번: 단지번호붙이기 (0) | 2022.09.18 |
[백준]JAVA - 1012번: 유기농 배추 (0) | 2022.09.17 |