하루에 한 문제
[프로그래머스] 타켓 넘버 -Java 본문
https://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+
programmers.co.kr
class Solution {
int answer;
public int solution(int[] numbers, int target) {
answer = 0;
dfs(numbers,target,0,0,numbers.length);
return answer;
}
private void dfs(int[] numbers, int target, int sum, int cnt, int length) {
if(cnt==length) {
if(sum==target) answer++;
return;
}
dfs(numbers, target, sum+numbers[cnt], cnt+1, length);
dfs(numbers, target, sum-numbers[cnt], cnt+1, length);
}
}소요시간 : 7분
전형적인 dfs문제였다.
그냥 문제에 나온 그대로 dfs를 통해서 더하고 빼주었다!
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스 Summer/Winter Coding] 영어 끝말잇기 -Java (0) | 2020.12.17 |
|---|---|
| [프로그래머스 2017 팁스다타운] 짝지어 제거하기 -Java (2) | 2020.12.17 |
| [프로그래머스 Summer/Winter Coding] 소수 만들기 -Java (0) | 2020.12.17 |
| [프로그래머스] N개의 최소공배수 -Java (0) | 2020.12.17 |
| [프로그래머스] H-Index -Java (0) | 2020.12.16 |
Comments