-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
동전교환문제 dfs 질문이있습니다
23.03.08 22:48 작성 조회수 258
0
실행하였을 때 생각나는 테스트케이스 모두 통과되는데 오답이라고 나오는 반례가 어떤 게 있을까요?....
import java.util.*;
class Main{
static int number, result;
static boolean check = false;
boolean flag=false;
public void DFS(int L,int sum, int[] arr){
if(sum>result || check) return;
if(sum==result){
System.out.println(L);
check = true;
}
else{
for(int i=0; i<number; i++) {
DFS(L + 1, sum+arr[i], arr);
}
}
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
number =kb.nextInt();
int[] arr = new int[number];
for(int i=0; i<number; i++){
arr[i] = kb.nextInt();
}
Arrays.sort(arr);
int first = 0;
int last = arr.length-1;
while(first<last){
int ch = arr[first];
arr[first++] = arr[last];
arr[last--] = ch;
}
result = kb.nextInt();
T.DFS( 0 , 0,arr);
}
}
답변을 작성해보세요.
0
답변 1