-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
연속부분수열 문제 질문드립니다.
22.11.23 12:54 작성 조회수 156
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
연속부분수열 문제를 dfs로 풀려고 하는데 답이 이상하게 나옵니다. 가지치기로 배열의 숫자들을 선택해서 더할때, 선택안하고 넘어갈 때 2가지로 구분해서 풀었습니다.
아니면 혹시 연속된 수열이라서 dfs로는 못 푸는 건가요??
import java.util.*;
public class Main {
public static int n,m,answer;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
int[] num = new int[n];
for(int i=0; i<n; i++)
num[i]=sc.nextInt();
dfs(0,0,num);
System.out.print(answer);
}
public static void dfs(int L, int sum, int[] a) {
if(sum>m) return;
if(L==n) {
if(sum==m) answer++;
}
else {
dfs(L+1, sum+a[L], a);
dfs(L+1, sum, a);
}
}
}
답변을 작성해보세요.
0
답변 1